1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "sandbox/win/src/policy_low_level.h"
6
7 #include <stddef.h>
8 #include <stdint.h>
9
10 #include <map>
11 #include <string>
12
13 namespace {
14
15 // A single rule can use at most this amount of memory.
16 const size_t kRuleBufferSize = 1024 * 4;
17
18 // The possible states of the string matching opcode generator.
19 enum {
20 PENDING_NONE,
21 PENDING_ASTERISK, // Have seen an '*' but have not generated an opcode.
22 PENDING_QMARK, // Have seen an '?' but have not generated an opcode.
23 };
24
25 // The category of the last character seen by the string matching opcode
26 // generator.
27 const uint32_t kLastCharIsNone = 0;
28 const uint32_t kLastCharIsAlpha = 1;
29 const uint32_t kLastCharIsWild = 2;
30 const uint32_t kLastCharIsAsterisk = kLastCharIsWild + 4;
31 const uint32_t kLastCharIsQuestionM = kLastCharIsWild + 8;
32
33 } // namespace
34
35 namespace sandbox {
36
LowLevelPolicy(PolicyGlobal * policy_store)37 LowLevelPolicy::LowLevelPolicy(PolicyGlobal* policy_store)
38 : policy_store_(policy_store) {}
39
40 // Adding a rule is nothing more than pushing it into an stl container. Done()
41 // is called for the rule in case the code that made the rule in the first
42 // place has not done it.
AddRule(IpcTag service,PolicyRule * rule)43 bool LowLevelPolicy::AddRule(IpcTag service, PolicyRule* rule) {
44 if (!rule->Done()) {
45 return false;
46 }
47
48 PolicyRule* local_rule = new PolicyRule(*rule);
49 RuleNode node = {local_rule, service};
50 rules_.push_back(node);
51 return true;
52 }
53
~LowLevelPolicy()54 LowLevelPolicy::~LowLevelPolicy() {
55 // Delete all the rules.
56 typedef std::list<RuleNode> RuleNodes;
57 for (RuleNodes::iterator it = rules_.begin(); it != rules_.end(); ++it) {
58 delete it->rule;
59 }
60 }
61
62 // Here is where the heavy byte shuffling is done. We take all the rules and
63 // 'compile' them into a single memory region. Now, the rules are in random
64 // order so the first step is to reorganize them into a stl map that is keyed
65 // by the service id and as a value contains a list with all the rules that
66 // belong to that service. Then we enter the big for-loop where we carve a
67 // memory zone for the opcodes and the data and call RebindCopy on each rule
68 // so they all end up nicely packed in the policy_store_.
Done()69 bool LowLevelPolicy::Done() {
70 typedef std::list<RuleNode> RuleNodes;
71 typedef std::list<const PolicyRule*> RuleList;
72 typedef std::map<IpcTag, RuleList> Mmap;
73 Mmap mmap;
74
75 for (RuleNodes::iterator it = rules_.begin(); it != rules_.end(); ++it) {
76 mmap[it->service].push_back(it->rule);
77 }
78
79 PolicyBuffer* current_buffer = &policy_store_->data[0];
80 char* buffer_end =
81 reinterpret_cast<char*>(current_buffer) + policy_store_->data_size;
82 size_t avail_size = policy_store_->data_size;
83
84 for (Mmap::iterator it = mmap.begin(); it != mmap.end(); ++it) {
85 IpcTag service = (*it).first;
86 if (static_cast<size_t>(service) >= kMaxServiceCount) {
87 return false;
88 }
89 policy_store_->entry[static_cast<size_t>(service)] = current_buffer;
90
91 RuleList::iterator rules_it = (*it).second.begin();
92 RuleList::iterator rules_it_end = (*it).second.end();
93
94 size_t svc_opcode_count = 0;
95
96 for (; rules_it != rules_it_end; ++rules_it) {
97 const PolicyRule* rule = (*rules_it);
98 size_t op_count = rule->GetOpcodeCount();
99
100 size_t opcodes_size = op_count * sizeof(PolicyOpcode);
101 if (avail_size < opcodes_size) {
102 return false;
103 }
104 size_t data_size = avail_size - opcodes_size;
105 PolicyOpcode* opcodes_start = ¤t_buffer->opcodes[svc_opcode_count];
106 if (!rule->RebindCopy(opcodes_start, opcodes_size, buffer_end,
107 &data_size)) {
108 return false;
109 }
110 size_t used = avail_size - data_size;
111 buffer_end -= used;
112 avail_size -= used;
113 svc_opcode_count += op_count;
114 }
115
116 current_buffer->opcode_count = svc_opcode_count;
117 size_t policy_buffers_occupied =
118 (svc_opcode_count * sizeof(PolicyOpcode)) / sizeof(current_buffer[0]);
119 current_buffer = ¤t_buffer[policy_buffers_occupied + 1];
120 }
121
122 return true;
123 }
124
PolicyRule(EvalResult action)125 PolicyRule::PolicyRule(EvalResult action) : action_(action), done_(false) {
126 char* memory = new char[sizeof(PolicyBuffer) + kRuleBufferSize];
127 buffer_ = reinterpret_cast<PolicyBuffer*>(memory);
128 buffer_->opcode_count = 0;
129 opcode_factory_ =
130 new OpcodeFactory(buffer_, kRuleBufferSize + sizeof(PolicyOpcode));
131 }
132
PolicyRule(const PolicyRule & other)133 PolicyRule::PolicyRule(const PolicyRule& other) {
134 if (this == &other)
135 return;
136 action_ = other.action_;
137 done_ = other.done_;
138 size_t buffer_size = sizeof(PolicyBuffer) + kRuleBufferSize;
139 char* memory = new char[buffer_size];
140 buffer_ = reinterpret_cast<PolicyBuffer*>(memory);
141 memcpy(buffer_, other.buffer_, buffer_size);
142
143 char* opcode_buffer = reinterpret_cast<char*>(&buffer_->opcodes[0]);
144 char* next_opcode = &opcode_buffer[GetOpcodeCount() * sizeof(PolicyOpcode)];
145 opcode_factory_ =
146 new OpcodeFactory(next_opcode, other.opcode_factory_->memory_size());
147 }
148
149 // This function get called from a simple state machine implemented in
150 // AddStringMatch() which passes the current state (in state) and it passes
151 // true in last_call if AddStringMatch() has finished processing the input
152 // pattern string and this would be the last call to generate any pending
153 // opcode. The skip_count is the currently accumulated number of '?' seen so
154 // far and once the associated opcode is generated this function sets it back
155 // to zero.
GenStringOpcode(RuleType rule_type,StringMatchOptions match_opts,uint16_t parameter,int state,bool last_call,int * skip_count,std::wstring * fragment)156 bool PolicyRule::GenStringOpcode(RuleType rule_type,
157 StringMatchOptions match_opts,
158 uint16_t parameter,
159 int state,
160 bool last_call,
161 int* skip_count,
162 std::wstring* fragment) {
163 // The last opcode must:
164 // 1) Always clear the context.
165 // 2) Preserve the negation.
166 // 3) Remove the 'OR' mode flag.
167 uint32_t options = kPolNone;
168 if (last_call) {
169 if (IF_NOT == rule_type) {
170 options = kPolClearContext | kPolNegateEval;
171 } else {
172 options = kPolClearContext;
173 }
174 } else if (IF_NOT == rule_type) {
175 options = kPolUseOREval | kPolNegateEval;
176 }
177
178 PolicyOpcode* op = nullptr;
179
180 // The fragment string contains the accumulated characters to match with, it
181 // never contains wildcards (unless they have been escaped) and while there
182 // is no fragment there is no new string match opcode to generate.
183 if (fragment->empty()) {
184 // There is no new opcode to generate but in the last call we have to fix
185 // the previous opcode because it was really the last but we did not know
186 // it at that time.
187 if (last_call && (buffer_->opcode_count > 0)) {
188 op = &buffer_->opcodes[buffer_->opcode_count - 1];
189 op->SetOptions(options);
190 }
191 return true;
192 }
193
194 if (PENDING_ASTERISK == state) {
195 if (last_call) {
196 op = opcode_factory_->MakeOpWStringMatch(parameter, fragment->c_str(),
197 kSeekToEnd, match_opts, options);
198 } else {
199 op = opcode_factory_->MakeOpWStringMatch(
200 parameter, fragment->c_str(), kSeekForward, match_opts, options);
201 }
202
203 } else if (PENDING_QMARK == state) {
204 op = opcode_factory_->MakeOpWStringMatch(parameter, fragment->c_str(),
205 *skip_count, match_opts, options);
206 *skip_count = 0;
207 } else {
208 if (last_call) {
209 match_opts = static_cast<StringMatchOptions>(EXACT_LENGTH | match_opts);
210 }
211 op = opcode_factory_->MakeOpWStringMatch(parameter, fragment->c_str(), 0,
212 match_opts, options);
213 }
214 if (!op)
215 return false;
216 ++buffer_->opcode_count;
217 fragment->clear();
218 return true;
219 }
220
AddStringMatch(RuleType rule_type,int16_t parameter,const wchar_t * string,StringMatchOptions match_opts)221 bool PolicyRule::AddStringMatch(RuleType rule_type,
222 int16_t parameter,
223 const wchar_t* string,
224 StringMatchOptions match_opts) {
225 if (done_) {
226 // Do not allow to add more rules after generating the action opcode.
227 return false;
228 }
229
230 const wchar_t* current_char = string;
231 uint32_t last_char = kLastCharIsNone;
232 int state = PENDING_NONE;
233 int skip_count = 0; // counts how many '?' we have seen in a row.
234 std::wstring fragment; // accumulates the non-wildcard part.
235
236 while (L'\0' != *current_char) {
237 switch (*current_char) {
238 case L'*':
239 if (kLastCharIsWild & last_char) {
240 // '**' and '&*' is an error.
241 return false;
242 }
243 if (!GenStringOpcode(rule_type, match_opts, parameter, state, false,
244 &skip_count, &fragment)) {
245 return false;
246 }
247 last_char = kLastCharIsAsterisk;
248 state = PENDING_ASTERISK;
249 break;
250 case L'?':
251 if (kLastCharIsAsterisk == last_char) {
252 // '*?' is an error.
253 return false;
254 }
255 if (!GenStringOpcode(rule_type, match_opts, parameter, state, false,
256 &skip_count, &fragment)) {
257 return false;
258 }
259 ++skip_count;
260 last_char = kLastCharIsQuestionM;
261 state = PENDING_QMARK;
262 break;
263 case L'/':
264 // Note: "/?" is an escaped '?'. Eat the slash and fall through.
265 if (L'?' == current_char[1]) {
266 ++current_char;
267 }
268 FALLTHROUGH;
269 default:
270 fragment += *current_char;
271 last_char = kLastCharIsAlpha;
272 }
273 ++current_char;
274 }
275
276 if (!GenStringOpcode(rule_type, match_opts, parameter, state, true,
277 &skip_count, &fragment)) {
278 return false;
279 }
280 return true;
281 }
282
AddNumberMatch(RuleType rule_type,int16_t parameter,uint32_t number,RuleOp comparison_op)283 bool PolicyRule::AddNumberMatch(RuleType rule_type,
284 int16_t parameter,
285 uint32_t number,
286 RuleOp comparison_op) {
287 if (done_) {
288 // Do not allow to add more rules after generating the action opcode.
289 return false;
290 }
291 uint32_t opts = (rule_type == IF_NOT) ? kPolNegateEval : kPolNone;
292
293 if (EQUAL == comparison_op) {
294 if (!opcode_factory_->MakeOpNumberMatch(parameter, number, opts))
295 return false;
296 } else if (AND == comparison_op) {
297 if (!opcode_factory_->MakeOpNumberAndMatch(parameter, number, opts))
298 return false;
299 }
300 ++buffer_->opcode_count;
301 return true;
302 }
303
Done()304 bool PolicyRule::Done() {
305 if (done_) {
306 return true;
307 }
308 if (!opcode_factory_->MakeOpAction(action_, kPolNone))
309 return false;
310 ++buffer_->opcode_count;
311 done_ = true;
312 return true;
313 }
314
RebindCopy(PolicyOpcode * opcode_start,size_t opcode_size,char * data_start,size_t * data_size) const315 bool PolicyRule::RebindCopy(PolicyOpcode* opcode_start,
316 size_t opcode_size,
317 char* data_start,
318 size_t* data_size) const {
319 size_t count = buffer_->opcode_count;
320 for (size_t ix = 0; ix != count; ++ix) {
321 if (opcode_size < sizeof(PolicyOpcode)) {
322 return false;
323 }
324 PolicyOpcode& opcode = buffer_->opcodes[ix];
325 *opcode_start = opcode;
326 if (OP_WSTRING_MATCH == opcode.GetID()) {
327 // For this opcode argument 0 is a delta to the string and argument 1
328 // is the length (in chars) of the string.
329 const wchar_t* str = opcode.GetRelativeString(0);
330 size_t str_len;
331 opcode.GetArgument(1, &str_len);
332 str_len = str_len * sizeof(wchar_t);
333 if ((*data_size) < str_len) {
334 return false;
335 }
336 *data_size -= str_len;
337 data_start -= str_len;
338 memcpy(data_start, str, str_len);
339 // Recompute the string displacement
340 ptrdiff_t delta = data_start - reinterpret_cast<char*>(opcode_start);
341 opcode_start->SetArgument(0, delta);
342 }
343 ++opcode_start;
344 opcode_size -= sizeof(PolicyOpcode);
345 }
346
347 return true;
348 }
349
~PolicyRule()350 PolicyRule::~PolicyRule() {
351 delete[] reinterpret_cast<char*>(buffer_);
352 delete opcode_factory_;
353 }
354
355 } // namespace sandbox
356