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: 61 virtual uint64_t GetBase() const { return 0; } 62 virtual uint32_t GetSize() const { return 0; } 63 virtual bool GetMemoryAtAddress(uint64_t address, uint8_t *value) const { 64 *value = address + 1; 65 return true; 66 } 67 virtual bool GetMemoryAtAddress(uint64_t address, uint16_t *value) const { 68 *value = address + 1; 69 return true; 70 } 71 virtual bool GetMemoryAtAddress(uint64_t address, uint32_t *value) const { 72 *value = address + 1; 73 return true; 74 } 75 virtual bool GetMemoryAtAddress(uint64_t address, uint64_t *value) const { 76 *value = address + 1; 77 return true; 78 } 79 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 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 399 int main(int argc, char **argv) { 400 BPLOG_INIT(&argc, &argv); 401 402 return RunTests() ? 0 : 1; 403 } 404
