src/breakpad/src/processor/postfix_evaluator_unittest.cc

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