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