1 // Copyright (c) 2010 Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 // * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 // postfix_evaluator_unittest.cc: Unit tests for PostfixEvaluator.
31 //
32 // Author: Mark Mentovai
33
34 #include <assert.h>
35 #include <stdio.h>
36
37 #include <map>
38 #include <string>
39
40 #include "processor/postfix_evaluator-inl.h"
41
42 #include "common/using_std_string.h"
43 #include "google_breakpad/common/breakpad_types.h"
44 #include "google_breakpad/processor/memory_region.h"
45 #include "processor/logging.h"
46
47
48 namespace {
49
50
51 using std::map;
52 using google_breakpad::MemoryRegion;
53 using google_breakpad::PostfixEvaluator;
54
55
56 // FakeMemoryRegion is used to test PostfixEvaluator's dereference (^)
57 // operator. The result of dereferencing a value is one greater than
58 // the value.
59 class FakeMemoryRegion : public MemoryRegion {
60 public:
GetBase() const61 virtual uint64_t GetBase() const { return 0; }
GetSize() const62 virtual uint32_t GetSize() const { return 0; }
GetMemoryAtAddress(uint64_t address,uint8_t * value) const63 virtual bool GetMemoryAtAddress(uint64_t address, uint8_t *value) const {
64 *value = address + 1;
65 return true;
66 }
GetMemoryAtAddress(uint64_t address,uint16_t * value) const67 virtual bool GetMemoryAtAddress(uint64_t address, uint16_t *value) const {
68 *value = address + 1;
69 return true;
70 }
GetMemoryAtAddress(uint64_t address,uint32_t * value) const71 virtual bool GetMemoryAtAddress(uint64_t address, uint32_t *value) const {
72 *value = address + 1;
73 return true;
74 }
GetMemoryAtAddress(uint64_t address,uint64_t * value) const75 virtual bool GetMemoryAtAddress(uint64_t address, uint64_t *value) const {
76 *value = address + 1;
77 return true;
78 }
Print() const79 virtual void Print() const {
80 assert(false);
81 }
82 };
83
84
85 struct EvaluateTest {
86 // Expression passed to PostfixEvaluator::Evaluate.
87 const string expression;
88
89 // True if the expression is expected to be evaluable, false if evaluation
90 // is expected to fail.
91 bool evaluable;
92 };
93
94
95 struct EvaluateTestSet {
96 // The dictionary used for all tests in the set.
97 PostfixEvaluator<unsigned int>::DictionaryType *dictionary;
98
99 // The list of tests.
100 const EvaluateTest *evaluate_tests;
101
102 // The number of tests.
103 unsigned int evaluate_test_count;
104
105 // Identifiers and their expected values upon completion of the Evaluate
106 // tests in the set.
107 map<string, unsigned int> *validate_data;
108 };
109
110
111 struct EvaluateForValueTest {
112 // Expression passed to PostfixEvaluator::Evaluate.
113 const string expression;
114
115 // True if the expression is expected to be evaluable, false if evaluation
116 // is expected to fail.
117 bool evaluable;
118
119 // If evaluable, the value we expect it to yield.
120 unsigned int value;
121 };
122
RunTests()123 static bool RunTests() {
124 // The first test set checks the basic operations and failure modes.
125 PostfixEvaluator<unsigned int>::DictionaryType dictionary_0;
126 const EvaluateTest evaluate_tests_0[] = {
127 { "$rAdd 2 2 + =", true }, // $rAdd = 2 + 2 = 4
128 { "$rAdd $rAdd 2 + =", true }, // $rAdd = $rAdd + 2 = 6
129 { "$rAdd 2 $rAdd + =", true }, // $rAdd = 2 + $rAdd = 8
130 { "99", false }, // put some junk on the stack...
131 { "$rAdd2 2 2 + =", true }, // ...and make sure things still work
132 { "$rAdd2\t2\n2 + =", true }, // same but with different whitespace
133 { "$rAdd2 2 2 + = ", true }, // trailing whitespace
134 { " $rAdd2 2 2 + =", true }, // leading whitespace
135 { "$rAdd2 2 2 + =", true }, // extra whitespace
136 { "$T0 2 = +", false }, // too few operands for add
137 { "2 + =", false }, // too few operands for add
138 { "2 +", false }, // too few operands for add
139 { "+", false }, // too few operands for add
140 { "^", false }, // too few operands for dereference
141 { "=", false }, // too few operands for assignment
142 { "2 =", false }, // too few operands for assignment
143 { "2 2 + =", false }, // too few operands for assignment
144 { "2 2 =", false }, // can't assign into a literal
145 { "k 2 =", false }, // can't assign into a constant
146 { "2", false }, // leftover data on stack
147 { "2 2 +", false }, // leftover data on stack
148 { "$rAdd", false }, // leftover data on stack
149 { "0 $T1 0 0 + =", false }, // leftover data on stack
150 { "$T2 $T2 2 + =", false }, // can't operate on an undefined value
151 { "$rMul 9 6 * =", true }, // $rMul = 9 * 6 = 54
152 { "$rSub 9 6 - =", true }, // $rSub = 9 - 6 = 3
153 { "$rDivQ 9 6 / =", true }, // $rDivQ = 9 / 6 = 1
154 { "$rDivM 9 6 % =", true }, // $rDivM = 9 % 6 = 3
155 { "$rDeref 9 ^ =", true }, // $rDeref = ^9 = 10 (FakeMemoryRegion)
156 { "$rAlign 36 8 @ =", true }, // $rAlign = 36 @ 8
157 { "$rAdd3 2 2 + =$rMul2 9 6 * =", true } // smashed-equals tokenization
158 };
159 map<string, unsigned int> validate_data_0;
160 validate_data_0["$rAdd"] = 8;
161 validate_data_0["$rAdd2"] = 4;
162 validate_data_0["$rSub"] = 3;
163 validate_data_0["$rMul"] = 54;
164 validate_data_0["$rDivQ"] = 1;
165 validate_data_0["$rDivM"] = 3;
166 validate_data_0["$rDeref"] = 10;
167 validate_data_0["$rAlign"] = 32;
168 validate_data_0["$rAdd3"] = 4;
169 validate_data_0["$rMul2"] = 54;
170
171 // The second test set simulates a couple of MSVC program strings.
172 // The data is fudged a little bit because the tests use FakeMemoryRegion
173 // instead of a real stack snapshot, but the program strings are real and
174 // the implementation doesn't know or care that the data is not real.
175 PostfixEvaluator<unsigned int>::DictionaryType dictionary_1;
176 dictionary_1["$ebp"] = 0xbfff0010;
177 dictionary_1["$eip"] = 0x10000000;
178 dictionary_1["$esp"] = 0xbfff0000;
179 dictionary_1[".cbSavedRegs"] = 4;
180 dictionary_1[".cbParams"] = 4;
181 dictionary_1[".raSearchStart"] = 0xbfff0020;
182 const EvaluateTest evaluate_tests_1[] = {
183 { "$T0 $ebp = $eip $T0 4 + ^ = $ebp $T0 ^ = $esp $T0 8 + = "
184 "$L $T0 .cbSavedRegs - = $P $T0 8 + .cbParams + =", true },
185 // Intermediate state: $T0 = 0xbfff0010, $eip = 0xbfff0015,
186 // $ebp = 0xbfff0011, $esp = 0xbfff0018,
187 // $L = 0xbfff000c, $P = 0xbfff001c
188 { "$T0 $ebp = $eip $T0 4 + ^ = $ebp $T0 ^ = $esp $T0 8 + = "
189 "$L $T0 .cbSavedRegs - = $P $T0 8 + .cbParams + = $ebx $T0 28 - ^ =",
190 true },
191 // Intermediate state: $T0 = 0xbfff0011, $eip = 0xbfff0016,
192 // $ebp = 0xbfff0012, $esp = 0xbfff0019,
193 // $L = 0xbfff000d, $P = 0xbfff001d,
194 // $ebx = 0xbffefff6
195 { "$T0 $ebp = $T2 $esp = $T1 .raSearchStart = $eip $T1 ^ = $ebp $T0 = "
196 "$esp $T1 4 + = $L $T0 .cbSavedRegs - = $P $T1 4 + .cbParams + = "
197 "$ebx $T0 28 - ^ =",
198 true }
199 };
200 map<string, unsigned int> validate_data_1;
201 validate_data_1["$T0"] = 0xbfff0012;
202 validate_data_1["$T1"] = 0xbfff0020;
203 validate_data_1["$T2"] = 0xbfff0019;
204 validate_data_1["$eip"] = 0xbfff0021;
205 validate_data_1["$ebp"] = 0xbfff0012;
206 validate_data_1["$esp"] = 0xbfff0024;
207 validate_data_1["$L"] = 0xbfff000e;
208 validate_data_1["$P"] = 0xbfff0028;
209 validate_data_1["$ebx"] = 0xbffefff7;
210 validate_data_1[".cbSavedRegs"] = 4;
211 validate_data_1[".cbParams"] = 4;
212
213 EvaluateTestSet evaluate_test_sets[] = {
214 { &dictionary_0, evaluate_tests_0,
215 sizeof(evaluate_tests_0) / sizeof(EvaluateTest), &validate_data_0 },
216 { &dictionary_1, evaluate_tests_1,
217 sizeof(evaluate_tests_1) / sizeof(EvaluateTest), &validate_data_1 },
218 };
219
220 unsigned int evaluate_test_set_count = sizeof(evaluate_test_sets) /
221 sizeof(EvaluateTestSet);
222
223 FakeMemoryRegion fake_memory;
224 PostfixEvaluator<unsigned int> postfix_evaluator =
225 PostfixEvaluator<unsigned int>(NULL, &fake_memory);
226
227 for (unsigned int evaluate_test_set_index = 0;
228 evaluate_test_set_index < evaluate_test_set_count;
229 ++evaluate_test_set_index) {
230 EvaluateTestSet *evaluate_test_set =
231 &evaluate_test_sets[evaluate_test_set_index];
232 const EvaluateTest *evaluate_tests = evaluate_test_set->evaluate_tests;
233 unsigned int evaluate_test_count = evaluate_test_set->evaluate_test_count;
234
235 // The same dictionary will be used for each test in the set. Earlier
236 // tests can affect the state of the dictionary for later tests.
237 postfix_evaluator.set_dictionary(evaluate_test_set->dictionary);
238
239 // Use a new validity dictionary for each test set.
240 PostfixEvaluator<unsigned int>::DictionaryValidityType assigned;
241
242 for (unsigned int evaluate_test_index = 0;
243 evaluate_test_index < evaluate_test_count;
244 ++evaluate_test_index) {
245 const EvaluateTest *evaluate_test = &evaluate_tests[evaluate_test_index];
246
247 // Do the test.
248 bool result = postfix_evaluator.Evaluate(evaluate_test->expression,
249 &assigned);
250 if (result != evaluate_test->evaluable) {
251 fprintf(stderr, "FAIL: evaluate set %d/%d, test %d/%d, "
252 "expression \"%s\", expected %s, observed %s\n",
253 evaluate_test_set_index, evaluate_test_set_count,
254 evaluate_test_index, evaluate_test_count,
255 evaluate_test->expression.c_str(),
256 evaluate_test->evaluable ? "evaluable" : "not evaluable",
257 result ? "evaluted" : "not evaluated");
258 return false;
259 }
260 }
261
262 // Validate the results.
263 for (map<string, unsigned int>::const_iterator validate_iterator =
264 evaluate_test_set->validate_data->begin();
265 validate_iterator != evaluate_test_set->validate_data->end();
266 ++validate_iterator) {
267 const string identifier = validate_iterator->first;
268 unsigned int expected_value = validate_iterator->second;
269
270 map<string, unsigned int>::const_iterator dictionary_iterator =
271 evaluate_test_set->dictionary->find(identifier);
272
273 // The identifier must exist in the dictionary.
274 if (dictionary_iterator == evaluate_test_set->dictionary->end()) {
275 fprintf(stderr, "FAIL: evaluate test set %d/%d, "
276 "validate identifier \"%s\", "
277 "expected %d, observed not found\n",
278 evaluate_test_set_index, evaluate_test_set_count,
279 identifier.c_str(), expected_value);
280 return false;
281 }
282
283 // The value in the dictionary must be the same as the expected value.
284 unsigned int observed_value = dictionary_iterator->second;
285 if (expected_value != observed_value) {
286 fprintf(stderr, "FAIL: evaluate test set %d/%d, "
287 "validate identifier \"%s\", "
288 "expected %d, observed %d\n",
289 evaluate_test_set_index, evaluate_test_set_count,
290 identifier.c_str(), expected_value, observed_value);
291 return false;
292 }
293
294 // The value must be set in the "assigned" dictionary if it was a
295 // variable. It must not have been assigned if it was a constant.
296 bool expected_assigned = identifier[0] == '$';
297 bool observed_assigned = false;
298 PostfixEvaluator<unsigned int>::DictionaryValidityType::const_iterator
299 iterator_assigned = assigned.find(identifier);
300 if (iterator_assigned != assigned.end()) {
301 observed_assigned = iterator_assigned->second;
302 }
303 if (expected_assigned != observed_assigned) {
304 fprintf(stderr, "FAIL: evaluate test set %d/%d, "
305 "validate assignment of \"%s\", "
306 "expected %d, observed %d\n",
307 evaluate_test_set_index, evaluate_test_set_count,
308 identifier.c_str(), expected_assigned, observed_assigned);
309 return false;
310 }
311 }
312 }
313
314 // EvaluateForValue tests.
315 PostfixEvaluator<unsigned int>::DictionaryType dictionary_2;
316 dictionary_2["$ebp"] = 0xbfff0010;
317 dictionary_2["$eip"] = 0x10000000;
318 dictionary_2["$esp"] = 0xbfff0000;
319 dictionary_2[".cbSavedRegs"] = 4;
320 dictionary_2[".cbParams"] = 4;
321 dictionary_2[".raSearchStart"] = 0xbfff0020;
322 const EvaluateForValueTest evaluate_for_value_tests_2[] = {
323 { "28907223", true, 28907223 }, // simple constant
324 { "89854293 40010015 +", true, 89854293 + 40010015 }, // arithmetic
325 { "-870245 8769343 +", true, 7899098 }, // negative constants
326 { "$ebp $esp - $eip +", true, 0x10000010 }, // variable references
327 { "18929794 34015074", false, 0 }, // too many values
328 { "$ebp $ebp 4 - =", false, 0 }, // too few values
329 { "$new $eip = $new", true, 0x10000000 }, // make new variable
330 { "$new 4 +", true, 0x10000004 }, // see prior assignments
331 { ".cfa 42 = 10", false, 0 } // can't set constants
332 };
333 const int evaluate_for_value_tests_2_size
334 = (sizeof (evaluate_for_value_tests_2)
335 / sizeof (evaluate_for_value_tests_2[0]));
336 map<string, unsigned int> validate_data_2;
337 validate_data_2["$eip"] = 0x10000000;
338 validate_data_2["$ebp"] = 0xbfff000c;
339 validate_data_2["$esp"] = 0xbfff0000;
340 validate_data_2["$new"] = 0x10000000;
341 validate_data_2[".cbSavedRegs"] = 4;
342 validate_data_2[".cbParams"] = 4;
343 validate_data_2[".raSearchStart"] = 0xbfff0020;
344
345 postfix_evaluator.set_dictionary(&dictionary_2);
346 for (int i = 0; i < evaluate_for_value_tests_2_size; i++) {
347 const EvaluateForValueTest *test = &evaluate_for_value_tests_2[i];
348 unsigned int result;
349 if (postfix_evaluator.EvaluateForValue(test->expression, &result)
350 != test->evaluable) {
351 fprintf(stderr, "FAIL: evaluate for value test %d, "
352 "expected evaluation to %s, but it %s\n",
353 i, test->evaluable ? "succeed" : "fail",
354 test->evaluable ? "failed" : "succeeded");
355 return false;
356 }
357 if (test->evaluable && result != test->value) {
358 fprintf(stderr, "FAIL: evaluate for value test %d, "
359 "expected value to be 0x%x, but it was 0x%x\n",
360 i, test->value, result);
361 return false;
362 }
363 }
364
365 for (map<string, unsigned int>::iterator v = validate_data_2.begin();
366 v != validate_data_2.end(); v++) {
367 map<string, unsigned int>::iterator a = dictionary_2.find(v->first);
368 if (a == dictionary_2.end()) {
369 fprintf(stderr, "FAIL: evaluate for value dictionary check: "
370 "expected dict[\"%s\"] to be 0x%x, but it was unset\n",
371 v->first.c_str(), v->second);
372 return false;
373 } else if (a->second != v->second) {
374 fprintf(stderr, "FAIL: evaluate for value dictionary check: "
375 "expected dict[\"%s\"] to be 0x%x, but it was 0x%x\n",
376 v->first.c_str(), v->second, a->second);
377 return false;
378 }
379 dictionary_2.erase(a);
380 }
381
382 map<string, unsigned int>::iterator remaining = dictionary_2.begin();
383 if (remaining != dictionary_2.end()) {
384 fprintf(stderr, "FAIL: evaluation of test expressions put unexpected "
385 "values in dictionary:\n");
386 for (; remaining != dictionary_2.end(); remaining++)
387 fprintf(stderr, " dict[\"%s\"] == 0x%x\n",
388 remaining->first.c_str(), remaining->second);
389 return false;
390 }
391
392 return true;
393 }
394
395
396 } // namespace
397
398
main(int argc,char ** argv)399 int main(int argc, char **argv) {
400 BPLOG_INIT(&argc, &argv);
401
402 return RunTests() ? 0 : 1;
403 }
404