1// Copyright (c) 2011 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// Fuzz testing for EncodedProgram serialized format and assembly.
6//
7// We would like some assurance that if an EncodedProgram is malformed we will
8// not crash.  The EncodedProgram could be malformed either due to malicious
9// attack to due to an error in patch generation.
10//
11// We try a lot of arbitrary modifications to the serialized form and make sure
12// that the outcome is not a crash.
13
14#include "base/test/test_suite.h"
15
16#include "courgette/base_test_unittest.h"
17#include "courgette/courgette.h"
18#include "courgette/streams.h"
19
20class DecodeFuzzTest : public BaseTest {
21 public:
22  void FuzzExe(const char *) const;
23
24 private:
25  void FuzzByte(const std::string& buffer, const std::string& output,
26                size_t index) const;
27  void FuzzBits(const std::string& buffer, const std::string& output,
28                size_t index, int bits_to_flip) const;
29
30  // Returns true if could assemble, false if rejected.
31  bool TryAssemble(const std::string& buffer, std::string* output) const;
32};
33
34// Loads an executable and does fuzz testing in the serialized format.
35void DecodeFuzzTest::FuzzExe(const char* file_name) const {
36  std::string file1 = FileContents(file_name);
37
38  const void* original_buffer = file1.c_str();
39  size_t original_length = file1.length();
40
41  courgette::AssemblyProgram* program = NULL;
42  const courgette::Status parse_status =
43      courgette::ParseDetectedExecutable(original_buffer, original_length,
44                                         &program);
45  EXPECT_EQ(courgette::C_OK, parse_status);
46
47  courgette::EncodedProgram* encoded = NULL;
48
49  const courgette::Status encode_status = Encode(program, &encoded);
50  EXPECT_EQ(courgette::C_OK, encode_status);
51
52  DeleteAssemblyProgram(program);
53
54  courgette::SinkStreamSet sinks;
55  const courgette::Status write_status = WriteEncodedProgram(encoded, &sinks);
56  EXPECT_EQ(courgette::C_OK, write_status);
57
58  DeleteEncodedProgram(encoded);
59
60  courgette::SinkStream sink;
61  bool can_collect = sinks.CopyTo(&sink);
62  EXPECT_TRUE(can_collect);
63
64  size_t length = sink.Length();
65
66  std::string base_buffer(reinterpret_cast<const char*>(sink.Buffer()), length);
67  std::string base_output;
68  bool ok = TryAssemble(base_buffer, &base_output);
69  EXPECT_TRUE(ok);
70
71  // Now we have a good serialized EncodedProgram in |base_buffer|. Time to
72  // fuzz.
73
74  // More intense fuzzing on the first part because it contains more control
75  // information like substeam lengths.
76  size_t position = 0;
77  for ( ;  position < 100 && position < length;  position += 1) {
78    FuzzByte(base_buffer, base_output, position);
79  }
80  // We would love to fuzz every position, but it takes too long.
81  for ( ;  position < length;  position += 900) {
82    FuzzByte(base_buffer, base_output, position);
83  }
84}
85
86// FuzzByte tries to break the EncodedProgram deserializer and assembler.  It
87// takes a good serialization of and EncodedProgram, flips some bits, and checks
88// that the behaviour is reasonable.  It has testing checks for unreasonable
89// behaviours.
90void DecodeFuzzTest::FuzzByte(const std::string& base_buffer,
91                              const std::string& base_output,
92                              size_t index) const {
93  printf("Fuzzing position %d\n", static_cast<int>(index));
94
95  // The following 10 values are a compromize between run time and coverage of
96  // the 255 'wrong' values at this byte position.
97
98  // 0xFF flips all the bits.
99  FuzzBits(base_buffer, base_output, index, 0xFF);
100  // 0x7F flips the most bits without changing Varint32 framing.
101  FuzzBits(base_buffer, base_output, index, 0x7F);
102  // These all flip one bit.
103  FuzzBits(base_buffer, base_output, index, 0x80);
104  FuzzBits(base_buffer, base_output, index, 0x40);
105  FuzzBits(base_buffer, base_output, index, 0x20);
106  FuzzBits(base_buffer, base_output, index, 0x10);
107  FuzzBits(base_buffer, base_output, index, 0x08);
108  FuzzBits(base_buffer, base_output, index, 0x04);
109  FuzzBits(base_buffer, base_output, index, 0x02);
110  FuzzBits(base_buffer, base_output, index, 0x01);
111}
112
113// FuzzBits tries to break the EncodedProgram deserializer and assembler.  It
114// takes a good serialization of and EncodedProgram, flips some bits, and checks
115// that the behaviour is reasonable.
116//
117// There are EXPECT calls to check for unreasonable behaviour.  These are
118// somewhat arbitrary in that the parameters cannot easily be derived from first
119// principles.  They may need updating as the serialized format evolves.
120void DecodeFuzzTest::FuzzBits(const std::string& base_buffer,
121                              const std::string& base_output,
122                              size_t index, int bits_to_flip) const {
123  std::string modified_buffer = base_buffer;
124  std::string modified_output;
125  modified_buffer[index] ^= bits_to_flip;
126
127  bool ok = TryAssemble(modified_buffer, &modified_output);
128
129  if (ok) {
130    // We normally expect TryAssemble to fail.  But sometimes it succeeds.
131    // What could have happened?  We changed one byte in the serialized form:
132    //
133    //  * If we changed one of the copied bytes, we would see a single byte
134    //    change in the output.
135    //  * If we changed an address table element, all the references to that
136    //    address would be different.
137    //  * If we changed a copy count, we would run out of data in some stream,
138    //    or leave data remaining, so should not be here.
139    //  * If we changed an origin address, it could affect all relocations based
140    //    off that address.  If no relocations were based off the address then
141    //    there will be no changes.
142    //  * If we changed an origin address, it could cause some abs32 relocs to
143    //    shift from one page to the next, changing the number and layout of
144    //    blocks in the base relocation table.
145
146    // Generated length could vary slightly due to base relocation table layout.
147    // In the worst case the number of base relocation blocks doubles, approx
148    // 12/4096 or 0.3% size of file.
149    size_t base_length = base_output.length();
150    size_t modified_length = modified_output.length();
151    ptrdiff_t diff = base_length - modified_length;
152    if (diff < -200 || diff > 200) {
153      EXPECT_EQ(base_length, modified_length);
154    }
155
156    size_t changed_byte_count = 0;
157    for (size_t i = 0;  i < base_length && i < modified_length; ++i) {
158      changed_byte_count += (base_output[i] != modified_output[i]);
159    }
160
161    if (index > 60) {                     // Beyond the origin addresses ...
162      EXPECT_NE(0U, changed_byte_count);   //   ... we expect some difference.
163    }
164    // Currently all changes are smaller than this number:
165    EXPECT_GE(45000U, changed_byte_count);
166  }
167}
168
169bool DecodeFuzzTest::TryAssemble(const std::string& buffer,
170                                 std::string* output) const {
171  courgette::EncodedProgram *encoded = NULL;
172  bool result = false;
173
174  courgette::SourceStreamSet sources;
175  bool can_get_source_streams = sources.Init(buffer.c_str(), buffer.length());
176  if (can_get_source_streams) {
177    const courgette::Status read_status =
178        ReadEncodedProgram(&sources, &encoded);
179    if (read_status == courgette::C_OK) {
180      courgette::SinkStream assembled;
181      const courgette::Status assemble_status = Assemble(encoded, &assembled);
182
183      if (assemble_status == courgette::C_OK) {
184        const void* assembled_buffer = assembled.Buffer();
185        size_t assembled_length = assembled.Length();
186
187        output->clear();
188        output->assign(reinterpret_cast<const char*>(assembled_buffer),
189                       assembled_length);
190        result = true;
191      }
192    }
193  }
194
195  DeleteEncodedProgram(encoded);
196
197  return result;
198}
199
200TEST_F(DecodeFuzzTest, All) {
201  FuzzExe("setup1.exe");
202  FuzzExe("elf-32-1.exe");
203}
204
205int main(int argc, char** argv) {
206  return base::TestSuite(argc, argv).Run();
207}
208