1 : // Copyright 2015 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : #include "syzygy/instrument/transforms/filler_transform.h"
16 :
17 : #include <vector>
18 :
19 : #include "base/memory/scoped_ptr.h"
20 : #include "gtest/gtest.h"
21 : #include "syzygy/assm/assembler_base.h"
22 : #include "syzygy/block_graph/basic_block.h"
23 : #include "syzygy/block_graph/basic_block_assembler.h"
24 : #include "syzygy/block_graph/basic_block_subgraph.h"
25 : #include "syzygy/block_graph/basic_block_test_util.h"
26 : #include "syzygy/block_graph/block_graph.h"
27 : #include "syzygy/instrument/transforms/unittest_util.h"
28 :
29 : namespace instrument {
30 : namespace transforms {
31 :
32 : namespace {
33 :
34 : using block_graph::BasicBlock;
35 : using block_graph::BlockGraph;
36 : using block_graph::BasicCodeBlock;
37 :
38 : const char kNopName[] = "NOP";
39 :
40 : // Finds instruction indices and sizes of every NOP in @p instructions and
41 : // stores the result in @p nop_indices. Returns the @p instructions count.
42 : size_t FindAllNops(BasicBlock::Instructions* instructions,
43 E : std::map<size_t, int>* nop_indices) {
44 E : size_t index = 0LL;
45 E : BasicBlock::Instructions::iterator inst_it = instructions->begin();
46 E : for (; inst_it != instructions->end(); ++inst_it, ++index) {
47 E : if (!::strcmp(inst_it->GetName(), kNopName))
48 E : (*nop_indices)[index] = inst_it->size();
49 E : }
50 E : return index;
51 E : }
52 :
53 : class FillerBasicBlockTransformTest : public testing::Test {
54 : public:
55 : typedef testing::Test Super;
56 : typedef FillerBasicBlockTransform::NopSizes NopSizes;
57 : typedef FillerBasicBlockTransform::NopSpec NopSpec;
58 :
59 : // Creates a new length @p n instruction list for testing.
60 E : void CreateInstructions(int n) {
61 : using assm::eax;
62 : using assm::ebp;
63 : using assm::esp;
64 : using assm::kSize32Bit;
65 :
66 E : instructions_.reset(new BasicBlock::Instructions);
67 E : if (n == 0)
68 E : return;
69 :
70 : block_graph::BasicBlockAssembler
71 E : assm(instructions_->begin(), instructions_.get());
72 E : bool setup_stack = false;
73 E : --n; // Reserve for ret.
74 E : if (n > 3) {
75 E : setup_stack = true;
76 E : n -= 3; // Reserve for stack frame setup.
77 : }
78 E : if (setup_stack) {
79 E : assm.push(ebp);
80 E : assm.mov(ebp, esp);
81 : }
82 E : for (; n > 0; --n)
83 E : assm.mov(eax, block_graph::Immediate(n, kSize32Bit));
84 E : if (setup_stack)
85 E : assm.pop(ebp);
86 E : assm.ret(0);
87 E : }
88 :
89 : protected:
90 : scoped_ptr<BasicBlock::Instructions> instructions_;
91 : };
92 :
93 : class TestFillerTransform : public FillerTransform {
94 : public:
95 E : TestFillerTransform(const std::set<std::string>& target_set,
96 : bool add_copy)
97 : : FillerTransform(target_set, add_copy) { }
98 : };
99 :
100 : class FillerTransformTest : public testing::TestDllTransformTest {
101 : public:
102 : typedef testing::TestDllTransformTest Super;
103 : typedef BlockGraph::Block::SourceRange SourceRange;
104 :
105 : // Finds all blocks whose names appear in @p target_set, and writes the
106 : // mapping fron name to block in @p result.
107 : void FindAllBlocks(
108 : const std::set<std::string>& target_set,
109 E : std::map<std::string, BlockGraph::Block*>* result) {
110 E : DCHECK(result && result->empty());
111 E : std::set<std::string> targets_remaining(target_set);
112 E : for (auto& it : block_graph_.blocks_mutable()) {
113 E : std::string block_name = it.second.name();
114 E : if (targets_remaining.find(block_name) != targets_remaining.end()) {
115 E : (*result)[block_name] = &it.second;
116 E : targets_remaining.erase(block_name);
117 : }
118 E : }
119 E : }
120 :
121 : // Verifies that @p instructions contains all expected NOPs except for NOPs
122 : // that would be inserted beyond the last instruction.
123 E : static void CheckNops(BasicBlock::Instructions* instructions) {
124 E : std::map<size_t, int> nop_indices;
125 E : size_t num_inst = FindAllNops(instructions, &nop_indices);
126 : // The checks here depend on how NopSpec is initialized in
127 : // FillerBasicBlockTransform! Currently we add NOP after every original
128 : // instruction, except for the last. So check every odd index for NOP.
129 E : EXPECT_EQ(num_inst / 2, nop_indices.size());
130 E : size_t expected_idx = 1;
131 E : for (const auto& it : nop_indices) {
132 E : EXPECT_EQ(expected_idx, it.first);
133 E : EXPECT_EQ(1, it.second); // NOP1.
134 E : expected_idx += 2;
135 : }
136 E : }
137 :
138 : // Verifies that all contiguous NOPs in @p instuctions are followed by a
139 : // non-NOP instruction, which shares the same source range as the NOP run.
140 E : static void CheckNopSourceRange(BasicBlock::Instructions* instructions) {
141 E : std::vector<SourceRange> range_queue;
142 E : BasicBlock::Instructions::iterator inst_it = instructions->begin();
143 E : for (; inst_it != instructions->end(); ++inst_it) {
144 E : if (!::strcmp(inst_it->GetName(), kNopName)) {
145 : // Found NOP: add to queue.
146 E : range_queue.push_back(inst_it->source_range());
147 E : } else {
148 : // Found non-NOP: verify stored ranges in the queue and then clear it.
149 E : for (SourceRange& nop_source_range : range_queue) {
150 E : EXPECT_EQ(inst_it->source_range(), nop_source_range);
151 : }
152 E : range_queue.clear();
153 : }
154 E : }
155 : // Expect there's no trailing NOP.
156 E : EXPECT_TRUE(range_queue.empty());
157 E : }
158 :
159 : // Applies the Filler Transform to specified @p target_set, and adds copy iff
160 : // @p add_copy is true. Verifies that the transform is successful.
161 : void ApplyFillerTransform(const std::set<std::string> target_set,
162 E : bool add_copy) {
163 E : ASSERT_NO_FATAL_FAILURE(DecomposeTestDll());
164 :
165 : // Apply the Filler Transform.
166 E : TestFillerTransform tx(target_set, add_copy);
167 E : tx.set_debug_friendly(true); // Copy source ranges to injected NOPs.
168 E : ASSERT_TRUE(block_graph::ApplyBlockGraphTransform(
169 : &tx, policy_, &block_graph_, header_block_));
170 :
171 : // Find and store target blocks for later verification.
172 E : EXPECT_EQ(target_set.size(), tx.num_targets_updated());
173 E : std::map<std::string, BlockGraph::Block*> target_map;
174 E : FindAllBlocks(target_set, &target_map);
175 E : EXPECT_EQ(target_set.size(), target_map.size());
176 :
177 : // Verify that each target has been properly modified.
178 E : for (auto& it : target_map) {
179 E : BlockGraph::Block* target_block = it.second;
180 :
181 : // Decompose target block to subgraph.
182 E : block_graph::BasicBlockSubGraph subgraph;
183 E : block_graph::BasicBlockDecomposer bb_decomposer(target_block, &subgraph);
184 E : ASSERT_TRUE(bb_decomposer.Decompose());
185 :
186 : // For each basic code block, verify that NOPs are properly placed.
187 : block_graph::BasicBlockSubGraph::BBCollection& basic_blocks =
188 E : subgraph.basic_blocks();
189 E : for (auto bb = basic_blocks.begin(); bb != basic_blocks.end(); ++bb) {
190 E : BasicCodeBlock* bc_block = BasicCodeBlock::Cast(*bb);
191 E : if (bc_block != nullptr) {
192 E : CheckNops(&bc_block->instructions());
193 E : CheckNopSourceRange(&bc_block->instructions());
194 : }
195 E : }
196 E : }
197 E : }
198 :
199 E : void ApplyFillerTransformTest(bool add_copy) {
200 : std::set<std::string> targets = {
201 : "Used::M",
202 : "TestUnusedFuncs"
203 E : };
204 :
205 E : ASSERT_NO_FATAL_FAILURE(ApplyFillerTransform(targets, add_copy));
206 :
207 : // Expect original targets to remain, and with copies if |add_copy|.
208 E : std::set<std::string> targets_with_copies(targets);
209 E : for (const auto& target : targets)
210 E : targets_with_copies.insert(target + "_copy");
211 : std::set<std::string> expected_results(
212 E : add_copy ? targets_with_copies : targets);
213 :
214 : // Search for original targets + copies, verify match with expected results.
215 E : std::map<std::string, BlockGraph::Block*> results;
216 E : FindAllBlocks(targets_with_copies, &results);
217 E : EXPECT_EQ(expected_results.size(), results.size());
218 E : for (const std::string target : expected_results)
219 E : EXPECT_NE(results.end(), results.find(target)) << target << " not found.";
220 E : }
221 : };
222 :
223 : } // namespace
224 :
225 : // Sanity check for helper CreateInstructions().
226 E : TEST_F(FillerBasicBlockTransformTest, CreateInstructions) {
227 E : for (int i = 0; i < 10; ++i) {
228 E : CreateInstructions(i);
229 E : size_t count = 0;
230 E : for (auto inst : *instructions_.get())
231 E : ++count;
232 E : EXPECT_EQ(i, count);
233 E : }
234 E : }
235 :
236 E : TEST_F(FillerBasicBlockTransformTest, InjectRegular) {
237 E : CreateInstructions(8);
238 : NopSpec nop_spec = {
239 : {1, NopSizes::NOP3},
240 : {2, NopSizes::NOP1},
241 : {3, NopSizes::NOP4},
242 : {6, NopSizes::NOP1},
243 : {8, NopSizes::NOP5},
244 E : {9, NopSizes::NOP9}};
245 E : FillerBasicBlockTransform::InjectNop(nop_spec, false, instructions_.get());
246 E : std::map<size_t, int> nop_indices;
247 E : EXPECT_EQ(8U + 6U, FindAllNops(instructions_.get(), &nop_indices));
248 E : EXPECT_EQ(6U, nop_indices.size());
249 E : EXPECT_EQ(3U, nop_indices[1]);
250 E : EXPECT_EQ(1U, nop_indices[2]);
251 E : EXPECT_EQ(4U, nop_indices[3]);
252 E : EXPECT_EQ(1U, nop_indices[6]);
253 E : EXPECT_EQ(5U, nop_indices[8]);
254 E : EXPECT_EQ(9U, nop_indices[9]);
255 E : }
256 :
257 E : TEST_F(FillerBasicBlockTransformTest, InjectToStart) {
258 E : CreateInstructions(5);
259 E : NopSpec nop_spec1 = {{0, NopSizes::NOP4}};
260 E : FillerBasicBlockTransform::InjectNop(nop_spec1, false, instructions_.get());
261 E : std::map<size_t, int> nop_indices1;
262 E : EXPECT_EQ(5U + 1U, FindAllNops(instructions_.get(), &nop_indices1));
263 E : EXPECT_EQ(1U, nop_indices1.size());
264 E : EXPECT_EQ(4U, nop_indices1[0]);
265 :
266 : // Inject another NOP, when a NOP already exists.
267 E : NopSpec nop_spec2 = {{0, NopSizes::NOP1}};
268 E : FillerBasicBlockTransform::InjectNop(nop_spec2, false, instructions_.get());
269 E : std::map<size_t, int> nop_indices2;
270 E : EXPECT_EQ(5U + 1U + 1U, FindAllNops(instructions_.get(), &nop_indices2));
271 E : EXPECT_EQ(2U, nop_indices2.size()); // New + existing.
272 E : EXPECT_EQ(1U, nop_indices2[0]); // From |nop_spec2|.
273 E : EXPECT_EQ(4U, nop_indices2[1]); // From |nop_spec1|.
274 E : }
275 :
276 E : TEST_F(FillerBasicBlockTransformTest, InjectToBeforeEnd) {
277 E : CreateInstructions(7);
278 E : NopSpec nop_spec = {{6, NopSizes::NOP2}};
279 E : FillerBasicBlockTransform::InjectNop(nop_spec, false, instructions_.get());
280 E : std::map<size_t, int> nop_indices;
281 E : EXPECT_EQ(7U + 1U, FindAllNops(instructions_.get(), &nop_indices));
282 E : EXPECT_EQ(1U, nop_indices.size());
283 E : EXPECT_EQ(2U, nop_indices[6]);
284 E : }
285 :
286 E : TEST_F(FillerBasicBlockTransformTest, CannotInjectBeyondEnd) {
287 E : CreateInstructions(7);
288 E : NopSpec nop_spec = {{7, NopSizes::NOP1}, {17, NopSizes::NOP1}};
289 E : FillerBasicBlockTransform::InjectNop(nop_spec, false, instructions_.get());
290 E : std::map<size_t, int> nop_indices;
291 E : EXPECT_EQ(7U, FindAllNops(instructions_.get(), &nop_indices));
292 E : EXPECT_EQ(0U, nop_indices.size());
293 E : }
294 :
295 E : TEST_F(FillerBasicBlockTransformTest, InjectToEmpty) {
296 E : CreateInstructions(0);
297 E : NopSpec nop_spec = {{0, NopSizes::NOP1}, {1, NopSizes::NOP2}};
298 E : FillerBasicBlockTransform::InjectNop(nop_spec, false, instructions_.get());
299 E : std::map<size_t, int> nop_indices;
300 E : EXPECT_EQ(0U, FindAllNops(instructions_.get(), &nop_indices));
301 E : EXPECT_EQ(0U, nop_indices.size());
302 E : }
303 :
304 E : TEST_F(FillerBasicBlockTransformTest, InjectToSingle) {
305 E : CreateInstructions(1);
306 : NopSpec nop_spec = {
307 : {0, NopSizes::NOP5},
308 : {1, NopSizes::NOP8},
309 E : {3, NopSizes::NOP2}}; // Gets ignored.
310 E : FillerBasicBlockTransform::InjectNop(nop_spec, false, instructions_.get());
311 E : std::map<size_t, int> nop_indices;
312 E : EXPECT_EQ(1U + 2U, FindAllNops(instructions_.get(), &nop_indices));
313 E : EXPECT_EQ(2U, nop_indices.size());
314 E : EXPECT_EQ(5U, nop_indices[0]);
315 E : EXPECT_EQ(8U, nop_indices[1]);
316 E : }
317 :
318 E : TEST_F(FillerBasicBlockTransformTest, InjectNone) {
319 E : CreateInstructions(7);
320 E : NopSpec nop_spec = {};
321 E : FillerBasicBlockTransform::InjectNop(nop_spec, false, instructions_.get());
322 E : std::map<size_t, int> nop_indices;
323 E : EXPECT_EQ(7U, FindAllNops(instructions_.get(), &nop_indices));
324 E : EXPECT_EQ(0U, nop_indices.size());
325 E : }
326 :
327 E : TEST_F(FillerBasicBlockTransformTest, InjectConsecutive) {
328 E : CreateInstructions(4);
329 : NopSpec nop_spec = {
330 : {0, NopSizes::NOP1},
331 : {1, NopSizes::NOP2},
332 : {2, NopSizes::NOP3},
333 : {3, NopSizes::NOP5},
334 : {4, NopSizes::NOP7},
335 E : {5, NopSizes::NOP11}};
336 E : FillerBasicBlockTransform::InjectNop(nop_spec, false, instructions_.get());
337 E : std::map<size_t, int> nop_indices;
338 E : EXPECT_EQ(4U + 6U, FindAllNops(instructions_.get(), &nop_indices));
339 E : EXPECT_EQ(6U, nop_indices.size());
340 E : EXPECT_EQ(1U, nop_indices[0]);
341 E : EXPECT_EQ(2U, nop_indices[1]);
342 E : EXPECT_EQ(3U, nop_indices[2]);
343 E : EXPECT_EQ(5U, nop_indices[3]);
344 E : EXPECT_EQ(7U, nop_indices[4]);
345 E : EXPECT_EQ(11U, nop_indices[5]);
346 E : }
347 :
348 E : TEST_F(FillerBasicBlockTransformTest, InjectAlternate) {
349 E : CreateInstructions(4);
350 : NopSpec nop_spec = {
351 : {0, NopSizes::NOP10},
352 : {2, NopSizes::NOP9},
353 : {4, NopSizes::NOP8},
354 : {6, NopSizes::NOP7},
355 : {8, NopSizes::NOP6}, // Gets ignored.
356 E : {10, NopSizes::NOP5}}; // Gets ignored.
357 E : FillerBasicBlockTransform::InjectNop(nop_spec, false, instructions_.get());
358 E : std::map<size_t, int> nop_indices;
359 E : EXPECT_EQ(4U + 4U, FindAllNops(instructions_.get(), &nop_indices));
360 E : EXPECT_EQ(4U, nop_indices.size());
361 E : EXPECT_EQ(10U, nop_indices[0]);
362 E : EXPECT_EQ(9U, nop_indices[2]);
363 E : EXPECT_EQ(8U, nop_indices[4]);
364 E : EXPECT_EQ(7U, nop_indices[6]);
365 E : }
366 :
367 E : TEST_F(FillerTransformTest, Apply) {
368 E : ASSERT_NO_FATAL_FAILURE(ApplyFillerTransformTest(true));
369 E : }
370 :
371 E : TEST_F(FillerTransformTest, ApplyNoAddCopy) {
372 E : ASSERT_NO_FATAL_FAILURE(ApplyFillerTransformTest(false));
373 E : }
374 :
375 : } // namespace transforms
376 : } // namespace instrument
|