1 // Copyright 2018 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 #include <stddef.h>
6 #include <stdint.h>
7
8 #include <optional>
9 #include <string>
10 #include <utility>
11 #include <vector>
12
13 #include "components/zucchini/imposed_ensemble_matcher.h"
14
15 #include "base/bind.h"
16 #include "base/callback_helpers.h"
17 #include "base/check_op.h"
18 #include "components/zucchini/buffer_view.h"
19 #include "components/zucchini/disassembler.h"
20 #include "components/zucchini/element_detection.h"
21 #include "components/zucchini/image_utils.h"
22 #include "testing/gtest/include/gtest/gtest.h"
23
24 namespace zucchini {
25
26 namespace {
27
28 // This test uses a mock archive format where regions are determined by their
29 // consecutive byte values rather than parsing real executables. In fact, since
30 // elements are imposed, only the first byte of the element is used to specify
31 // executable type of the mock data:
32 // - 'W' and 'w' specify kExeTypeWin32X86.
33 // - 'E' and 'e' specify kExeTypeElfX86.
34 // - Everything else specify kExeTypeUnknown.
35 class TestElementDetector {
36 public:
TestElementDetector()37 TestElementDetector() {}
38
Run(ConstBufferView image) const39 std::optional<Element> Run(ConstBufferView image) const {
40 DCHECK_GT(image.size(), 0U);
41 char first_char = *image.begin();
42 if (first_char == 'W' || first_char == 'w')
43 return Element(image.local_region(), kExeTypeWin32X86);
44 if (first_char == 'E' || first_char == 'e')
45 return Element(image.local_region(), kExeTypeElfX86);
46 return std::nullopt;
47 }
48 };
49
50 } // namespace
51
TEST(ImposedMatchParserTest,ImposedMatchParser)52 TEST(ImposedMatchParserTest, ImposedMatchParser) {
53 std::vector<uint8_t> old_data;
54 std::vector<uint8_t> new_data;
55 auto populate = [](const std::string& s, std::vector<uint8_t>* data) {
56 for (char ch : s)
57 data->push_back(static_cast<uint8_t>(ch));
58 };
59 // Pos: 11111111
60 // 012345678901234567
61 populate("1WW222EEEE", &old_data);
62 populate("33eee2222222wwww44", &new_data);
63
64 ConstBufferView old_image(&old_data[0], old_data.size());
65 ConstBufferView new_image(&new_data[0], new_data.size());
66
67 TestElementDetector detector;
68
69 // Reusable output values.
70 std::string prev_imposed_matches;
71 ImposedMatchParser::Status status;
72 size_t num_identical;
73 std::vector<ElementMatch> matches;
74 std::vector<ElementMatch> bad_matches;
75
76 auto run_test = [&](const std::string& imposed_matches) -> bool {
77 prev_imposed_matches = imposed_matches;
78 status = ImposedMatchParser::kSuccess;
79 num_identical = 0;
80 matches.clear();
81 bad_matches.clear();
82 ImposedMatchParser parser;
83 status = parser.Parse(imposed_matches, old_image, new_image,
84 base::BindRepeating(&TestElementDetector::Run,
85 base::Unretained(&detector)));
86 num_identical = parser.num_identical();
87 matches = std::move(*parser.mutable_matches());
88 bad_matches = std::move(*parser.mutable_bad_matches());
89 return status == ImposedMatchParser::kSuccess;
90 };
91
92 auto run_check = [&](const ElementMatch& match, ExecutableType exe_type,
93 offset_t old_offset, size_t old_size,
94 offset_t new_offset, size_t new_size) {
95 EXPECT_EQ(exe_type, match.exe_type()) << prev_imposed_matches;
96 EXPECT_EQ(exe_type, match.old_element.exe_type) << prev_imposed_matches;
97 EXPECT_EQ(old_offset, match.old_element.offset) << prev_imposed_matches;
98 EXPECT_EQ(old_size, match.old_element.size) << prev_imposed_matches;
99 EXPECT_EQ(exe_type, match.new_element.exe_type) << prev_imposed_matches;
100 EXPECT_EQ(new_offset, match.new_element.offset) << prev_imposed_matches;
101 EXPECT_EQ(new_size, match.new_element.size) << prev_imposed_matches;
102 };
103
104 // Empty string: Vacuous but valid.
105 EXPECT_TRUE(run_test(""));
106 EXPECT_EQ(0U, num_identical);
107 EXPECT_EQ(0U, matches.size());
108 EXPECT_EQ(0U, bad_matches.size());
109
110 // Full matches. Different permutations give same result.
111 for (const std::string& imposed_matches :
112 {"1+2=12+4,4+2=5+2,6+4=2+3", "1+2=12+4,6+4=2+3,4+2=5+2",
113 "4+2=5+2,1+2=12+4,6+4=2+3", "4+2=5+2,6+4=2+3,1+2=12+4",
114 "6+4=2+3,1+2=12+4,4+2=5+2", "6+4=2+3,1+2=12+4,4+2=5+2"}) {
115 EXPECT_TRUE(run_test(imposed_matches));
116 EXPECT_EQ(1U, num_identical); // "4+2=5+2"
117 EXPECT_EQ(2U, matches.size());
118 // Results are sorted by "new" offsets.
119 run_check(matches[0], kExeTypeElfX86, 6, 4, 2, 3);
120 run_check(matches[1], kExeTypeWin32X86, 1, 2, 12, 4);
121 EXPECT_EQ(0U, bad_matches.size());
122 }
123
124 // Single subregion match.
125 EXPECT_TRUE(run_test("1+2=12+4"));
126 EXPECT_EQ(0U, num_identical);
127 EXPECT_EQ(1U, matches.size());
128 run_check(matches[0], kExeTypeWin32X86, 1, 2, 12, 4);
129 EXPECT_EQ(0U, bad_matches.size());
130
131 // Single subregion match. We're lax with redundant 0.
132 EXPECT_TRUE(run_test("6+04=02+10"));
133 EXPECT_EQ(0U, num_identical);
134 EXPECT_EQ(1U, matches.size());
135 run_check(matches[0], kExeTypeElfX86, 6, 4, 2, 10);
136 EXPECT_EQ(0U, bad_matches.size());
137
138 // Successive elements, no overlap.
139 EXPECT_TRUE(run_test("1+1=12+1,2+1=13+1"));
140 EXPECT_EQ(0U, num_identical);
141 EXPECT_EQ(2U, matches.size());
142 run_check(matches[0], kExeTypeWin32X86, 1, 1, 12, 1);
143 run_check(matches[1], kExeTypeWin32X86, 2, 1, 13, 1);
144 EXPECT_EQ(0U, bad_matches.size());
145
146 // Overlap in "old" file is okay.
147 EXPECT_TRUE(run_test("1+2=12+2,1+2=14+2"));
148 EXPECT_EQ(0U, num_identical);
149 EXPECT_EQ(2U, matches.size());
150 run_check(matches[0], kExeTypeWin32X86, 1, 2, 12, 2);
151 run_check(matches[1], kExeTypeWin32X86, 1, 2, 14, 2);
152 EXPECT_EQ(0U, bad_matches.size());
153
154 // Entire files: Have unknown type, so are recognized as such, and ignored.
155 EXPECT_TRUE(run_test("0+10=0+18"));
156 EXPECT_EQ(0U, num_identical);
157 EXPECT_EQ(0U, matches.size());
158 EXPECT_EQ(1U, bad_matches.size());
159 run_check(bad_matches[0], kExeTypeUnknown, 0, 10, 0, 18);
160
161 // Forgive matches that mix known type with unknown type.
162 EXPECT_TRUE(run_test("1+2=0+18"));
163 EXPECT_EQ(0U, num_identical);
164 EXPECT_EQ(0U, matches.size());
165 EXPECT_EQ(1U, bad_matches.size());
166 run_check(bad_matches[0], kExeTypeUnknown, 1, 2, 0, 18);
167
168 EXPECT_TRUE(run_test("0+10=12+4"));
169 EXPECT_EQ(0U, num_identical);
170 EXPECT_EQ(0U, matches.size());
171 EXPECT_EQ(1U, bad_matches.size());
172 run_check(bad_matches[0], kExeTypeUnknown, 0, 10, 12, 4);
173
174 // Test invalid delimiter.
175 for (const std::string& imposed_matches :
176 {"1+2=12+4,4+2=5+2x", "1+2=12+4 4+2=5+2", "1+2=12+4,4+2=5+2 ",
177 "1+2=12+4 "}) {
178 EXPECT_FALSE(run_test(imposed_matches));
179 EXPECT_EQ(ImposedMatchParser::kInvalidDelimiter, status);
180 }
181
182 // Test parse errors, including uint32_t overflow.
183 for (const std::string& imposed_matches :
184 {"x1+2=12+4,4+2=5+2,6+4=2+3", "x1+2=12+4,4+2=5+2,6+4=2+3x", ",", " ",
185 "+2=12+4", "1+2+12+4", "1=2+12+4", " 1+2=12+4", "1+2= 12+4", "1", "1+2",
186 "1+2=", "1+2=12", "1+2=12+", "4294967296+2=12+4"}) {
187 EXPECT_FALSE(run_test(imposed_matches));
188 EXPECT_EQ(ImposedMatchParser::kParseError, status);
189 }
190
191 // Test bound errors, include 0-size.
192 for (const std::string& imposed_matches :
193 {"1+10=12+4", "1+2=12+7", "0+11=0+18", "0+12=0+17", "10+1=0+18",
194 "0+10=18+1", "0+0=0+18", "0+10=0+0", "1000000000+1=0+1000000000"}) {
195 EXPECT_FALSE(run_test(imposed_matches));
196 EXPECT_EQ(ImposedMatchParser::kOutOfBound, status);
197 }
198
199 // Test overlap errors. Matches that get ignored are still tested.
200 for (const std::string& imposed_matches :
201 {"1+2=12+4,4+2=5+2,6+4=2+4", "0+10=0+18,1+2=12+4", "6+4=2+10,3+2=5+2"}) {
202 EXPECT_FALSE(run_test(imposed_matches));
203 EXPECT_EQ(ImposedMatchParser::kOverlapInNew, status);
204 }
205
206 // Test type mismatch errors.
207 EXPECT_FALSE(run_test("1+2=2+3"));
208 EXPECT_EQ(ImposedMatchParser::kTypeMismatch, status);
209
210 EXPECT_FALSE(run_test("6+4=12+4"));
211 EXPECT_EQ(ImposedMatchParser::kTypeMismatch, status);
212 }
213
214 } // namespace zucchini
215