1 : // Copyright 2012 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/block_graph/block_util.h"
16 :
17 : #include "gtest/gtest.h"
18 : #include "syzygy/block_graph/basic_block_assembler.h"
19 : #include "syzygy/block_graph/basic_block_test_util.h"
20 :
21 : namespace block_graph {
22 :
23 : namespace {
24 :
25 : class BlockUtilTest: public testing::Test {
26 : public:
27 : BlockUtilTest()
28 : : bb_("foo"),
29 E : start_addr_(0xF00D) {
30 E : }
31 :
32 E : void TestAttributes(BlockGraph::BlockAttributes attributes, bool expected) {
33 E : BlockGraph::Block* code = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c");
34 E : code->set_attributes(attributes);
35 E : ASSERT_EQ(expected, CodeBlockAttributesAreBasicBlockSafe(code));
36 E : }
37 :
38 E : BlockGraph::Size AddInstructions(bool add_source_ranges) {
39 : using core::eax;
40 : using core::ebp;
41 : using core::esp;
42 :
43 E : BasicBlockAssembler assm(bb_.instructions().begin(), &bb_.instructions());
44 :
45 E : assm.push(ebp);
46 E : assm.mov(ebp, esp);
47 E : assm.mov(eax, Operand(ebp, Displacement(8)));
48 E : assm.pop(ebp);
49 : // assm.ret(0);
50 :
51 E : BasicBlock::Instructions::iterator inst_it(bb_.instructions().begin());
52 E : BlockGraph::RelativeAddress next_addr(start_addr_);
53 :
54 E : BasicBlock::Offset next_offs = 0;
55 E : for (; inst_it != bb_.instructions().end(); ++inst_it) {
56 E : if (add_source_ranges)
57 : inst_it->set_source_range(
58 E : Instruction::SourceRange(next_addr, inst_it->size()));
59 :
60 E : next_addr += inst_it->size();
61 E : next_offs += inst_it->size();
62 E : }
63 :
64 E : BasicBlockReference ref(BlockGraph::PC_RELATIVE_REF, 4, &bb_);
65 : bb_.successors().push_back(
66 E : Successor(Successor::kConditionAbove, ref, 5));
67 E : next_offs += 5;
68 :
69 E : if (add_source_ranges)
70 : bb_.successors().back().set_source_range(
71 E : Successor::SourceRange(next_addr, 5));
72 :
73 : bb_.successors().push_back(
74 E : Successor(Successor::kConditionBelowOrEqual, ref, 0));
75 :
76 E : return next_offs;
77 E : }
78 :
79 : protected:
80 : BlockGraph image_;
81 : BlockGraph::RelativeAddress start_addr_;
82 : BasicCodeBlock bb_;
83 : };
84 :
85 : } // namespace
86 :
87 E : TEST_F(BlockUtilTest, CodeBlockAttributesAreBasicBlockSafeGapBlock) {
88 E : ASSERT_NO_FATAL_FAILURE(TestAttributes(BlockGraph::GAP_BLOCK, false));
89 E : }
90 :
91 E : TEST_F(BlockUtilTest, CodeBlockAttributesAreBasicBlockSafePaddingBlock) {
92 E : ASSERT_NO_FATAL_FAILURE(TestAttributes(BlockGraph::PADDING_BLOCK, false));
93 E : }
94 :
95 E : TEST_F(BlockUtilTest, CodeBlockAttributesAreBasicBlockSafeHasInlineAssembly) {
96 : ASSERT_NO_FATAL_FAILURE(TestAttributes(BlockGraph::HAS_INLINE_ASSEMBLY,
97 E : false));
98 E : }
99 :
100 E : TEST_F(BlockUtilTest, CodeBlockAttributesAreBasicBlockSafeUnsupportedCompiler) {
101 : ASSERT_NO_FATAL_FAILURE(TestAttributes(
102 E : BlockGraph::BUILT_BY_UNSUPPORTED_COMPILER, false));
103 E : }
104 :
105 E : TEST_F(BlockUtilTest, CodeBlockAttributesAreBasicBlockSafeErroredDisassembly) {
106 : ASSERT_NO_FATAL_FAILURE(TestAttributes(BlockGraph::ERRORED_DISASSEMBLY,
107 E : false));
108 E : }
109 :
110 E : TEST_F(BlockUtilTest, CodeBlockAttributesAreBasicBlockSafeExceptionHandling) {
111 : ASSERT_NO_FATAL_FAILURE(TestAttributes(BlockGraph::HAS_EXCEPTION_HANDLING,
112 E : false));
113 E : }
114 :
115 E : TEST_F(BlockUtilTest, CodeBlockAttributesAreBasicBlockSafeDisassembledPastEnd) {
116 : ASSERT_NO_FATAL_FAILURE(TestAttributes(BlockGraph::DISASSEMBLED_PAST_END,
117 E : false));
118 E : }
119 :
120 E : TEST_F(BlockUtilTest, CodeBlockAttributesAreBasicBlockSafeBuiltBySyzygy) {
121 : ASSERT_NO_FATAL_FAILURE(TestAttributes(
122 E : BlockGraph::HAS_INLINE_ASSEMBLY | BlockGraph::BUILT_BY_SYZYGY, true));
123 E : }
124 :
125 E : TEST_F(BlockUtilTest, GetBasicBlockSourceRangeEmptyFails) {
126 E : BlockGraph::Size instr_len = AddInstructions(false);
127 :
128 E : BlockGraph::Block::SourceRange source_range;
129 E : ASSERT_FALSE(GetBasicBlockSourceRange(bb_, &source_range));
130 E : EXPECT_EQ(0, source_range.size());
131 E : }
132 :
133 E : TEST_F(BlockUtilTest, GetBasicBlockSourceRangeNonContiguousFails) {
134 E : BlockGraph::Size instr_len = AddInstructions(true);
135 :
136 : // Make the range non-contiguous by pushing the successor out one byte.
137 : BlockGraph::Block::SourceRange range =
138 E : bb_.successors().front().source_range();
139 : bb_.successors().front().set_source_range(
140 E : BlockGraph::Block::SourceRange(range.start() + 1, range.size()));
141 :
142 E : BlockGraph::Block::SourceRange source_range;
143 E : ASSERT_FALSE(GetBasicBlockSourceRange(bb_, &source_range));
144 E : EXPECT_EQ(0, source_range.size());
145 E : }
146 :
147 E : TEST_F(BlockUtilTest, GetBasicBlockSourceRangeSequentialSucceeds) {
148 E : BlockGraph::Size instr_len = AddInstructions(true);
149 :
150 E : BlockGraph::Block::SourceRange source_range;
151 E : ASSERT_TRUE(GetBasicBlockSourceRange(bb_, &source_range));
152 : BlockGraph::Block::SourceRange expected_range(
153 E : BlockGraph::RelativeAddress(0xF00D), instr_len);
154 E : EXPECT_EQ(expected_range, source_range);
155 E : }
156 :
157 E : TEST_F(BlockUtilTest, GetBasicBlockSourceRangeNonSequentialSucceeds) {
158 E : BlockGraph::Size instr_len = AddInstructions(true);
159 :
160 : // Shuffle the ranges by flipping the first and last ranges.
161 E : BlockGraph::Block::SourceRange temp = bb_.successors().front().source_range();
162 : bb_.successors().front().set_source_range(
163 E : bb_.instructions().front().source_range());
164 E : bb_.instructions().front().set_source_range(temp);
165 :
166 E : BlockGraph::Block::SourceRange source_range;
167 E : ASSERT_TRUE(GetBasicBlockSourceRange(bb_, &source_range));
168 : BlockGraph::Block::SourceRange expected_range(
169 E : BlockGraph::RelativeAddress(0xF00D), instr_len);
170 E : EXPECT_EQ(expected_range, source_range);
171 E : }
172 :
173 E : TEST_F(BlockUtilTest, GetBasicBlockSourceRangePrependInstructionsSucceeds) {
174 E : BlockGraph::Size instr_len = AddInstructions(true);
175 :
176 : // Prepend some instrumentation-like code.
177 E : BasicBlockAssembler assm(bb_.instructions().begin(), &bb_.instructions());
178 E : assm.push(Immediate(0xBADF00D));
179 E : assm.call(Displacement(&bb_));
180 :
181 E : BlockGraph::Block::SourceRange source_range;
182 E : ASSERT_TRUE(GetBasicBlockSourceRange(bb_, &source_range));
183 : BlockGraph::Block::SourceRange expected_range(
184 E : BlockGraph::RelativeAddress(0xF00D), instr_len);
185 E : EXPECT_EQ(expected_range, source_range);
186 E : }
187 :
188 E : TEST_F(BlockUtilTest, IsUnsafeReference) {
189 : // Some safe blocks.
190 E : BlockGraph::Block* s1 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "s1");
191 E : BlockGraph::Block* s2 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "s2");
192 :
193 : // Some unsafe blocks.
194 E : BlockGraph::Block* u1 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "u1");
195 E : u1->set_attribute(BlockGraph::HAS_INLINE_ASSEMBLY);
196 E : BlockGraph::Block* u2 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "u2");
197 E : u2->set_attribute(BlockGraph::BUILT_BY_UNSUPPORTED_COMPILER);
198 :
199 : // If neither or only one has an unsafe attribute then it's not unsafe.
200 : EXPECT_FALSE(IsUnsafeReference(s1, BlockGraph::Reference(
201 : BlockGraph::PC_RELATIVE_REF,
202 : BlockGraph::Reference::kMaximumSize,
203 E : s2, 0, 0)));
204 : EXPECT_FALSE(IsUnsafeReference(s1, BlockGraph::Reference(
205 : BlockGraph::PC_RELATIVE_REF,
206 : BlockGraph::Reference::kMaximumSize,
207 E : u1, 0, 0)));
208 : EXPECT_FALSE(IsUnsafeReference(u2, BlockGraph::Reference(
209 : BlockGraph::PC_RELATIVE_REF,
210 : BlockGraph::Reference::kMaximumSize,
211 E : s2, 0, 0)));
212 :
213 : // If the reference points to a non-zero offset then it's unsafe.
214 : EXPECT_TRUE(IsUnsafeReference(s1, BlockGraph::Reference(
215 : BlockGraph::PC_RELATIVE_REF,
216 : BlockGraph::Reference::kMaximumSize,
217 E : s2, 4, 4)));
218 :
219 : // If both the referring and referred blocks have unsafe attributes,
220 : // the reference is unsafe.
221 : EXPECT_TRUE(IsUnsafeReference(u1, BlockGraph::Reference(
222 : BlockGraph::PC_RELATIVE_REF,
223 : BlockGraph::Reference::kMaximumSize,
224 E : u2, 0, 0)));
225 E : }
226 :
227 E : TEST_F(BlockUtilTest, CheckNoUnexpectedStackFrameManipulation) {
228 E : BasicBlockSubGraph bbsg;
229 E : BasicCodeBlock* bb = bbsg.AddBasicCodeBlock("dummy");
230 :
231 : // Prepend some instrumentation with a conventional calling convention.
232 E : BasicBlockAssembler assm(bb->instructions().begin(), &bb->instructions());
233 E : assm.push(core::ebp);
234 E : assm.mov(core::ebp, core::esp);
235 E : assm.mov(core::eax, Operand(core::ebp, Displacement(8)));
236 E : assm.pop(core::ebp);
237 E : assm.ret(0);
238 :
239 E : EXPECT_FALSE(HasUnexpectedStackFrameManipulation(&bbsg));
240 E : }
241 :
242 E : TEST_F(BlockUtilTest, CheckInvalidInstructionUnexpectedStackFrameManipulation) {
243 E : BasicBlockSubGraph bbsg;
244 E : BasicCodeBlock* bb = bbsg.AddBasicCodeBlock("dummy");
245 :
246 : // Prepend some instrumentation with a conventional calling convention.
247 E : BasicBlockAssembler assm(bb->instructions().begin(), &bb->instructions());
248 E : assm.push(core::ebp);
249 E : assm.mov(core::ebp, core::esp);
250 : // The instruction LEA is invalid stack frame manipulation.
251 E : assm.lea(core::ebp, Operand(core::ebp, Displacement(8)));
252 E : assm.pop(core::ebp);
253 E : assm.ret(0);
254 :
255 E : EXPECT_TRUE(HasUnexpectedStackFrameManipulation(&bbsg));
256 E : }
257 :
258 E : TEST_F(BlockUtilTest, CheckInvalidRegisterUnexpectedStackFrameManipulation) {
259 E : BasicBlockSubGraph bbsg;
260 E : BasicCodeBlock* bb = bbsg.AddBasicCodeBlock("dummy");
261 :
262 : // Prepend some instrumentation with a conventional calling convention.
263 E : BasicBlockAssembler assm(bb->instructions().begin(), &bb->instructions());
264 E : assm.push(core::ebp);
265 : // The instruction MOV use an invalid register EAX.
266 E : assm.mov(core::ebp, core::eax);
267 E : assm.lea(core::ebp, Operand(core::ebp, Displacement(8)));
268 E : assm.pop(core::ebp);
269 E : assm.ret(0);
270 :
271 E : EXPECT_TRUE(HasUnexpectedStackFrameManipulation(&bbsg));
272 E : }
273 :
274 : namespace {
275 :
276 : // A utility class for using the test data built around the function in
277 : // basic_block_assembly_func.asm.
278 : class BlockUtilOnTestDataTest : public testing::BasicBlockTest {
279 : public:
280 E : virtual void SetUp() OVERRIDE {
281 E : BasicBlockTest::SetUp();
282 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
283 E : }
284 : };
285 :
286 : } // namespace
287 :
288 E : TEST_F(BlockUtilOnTestDataTest, GetJumpTableSize) {
289 : block_graph::BlockGraph::BlockMap::const_iterator block_iter =
290 E : block_graph_.blocks().begin();
291 :
292 E : size_t table_size = 0;
293 E : bool table_found = false;
294 :
295 : // Iterates over the blocks of the block_graph. We expect to find only one
296 : // block containing one jump table.
297 E : for (; block_iter != block_graph_.blocks().end(); ++ block_iter) {
298 E : if (block_iter->second.type() != BlockGraph::CODE_BLOCK)
299 E : continue;
300 :
301 : // Iterates over the labels of the block to find the jump tables.
302 : BlockGraph::Block::LabelMap::const_iterator iter_label =
303 E : block_iter->second.labels().begin();
304 E : for (; iter_label != block_iter->second.labels().end();++iter_label) {
305 E : if (!iter_label->second.has_attributes(BlockGraph::JUMP_TABLE_LABEL))
306 E : continue;
307 :
308 : // There's only one jump table in the test data.
309 E : EXPECT_FALSE(table_found);
310 E : table_found = true;
311 :
312 : EXPECT_TRUE(block_graph::GetJumpTableSize(&block_iter->second,
313 : iter_label,
314 E : &table_size));
315 E : }
316 E : }
317 E : EXPECT_EQ(3U, table_size);
318 E : }
319 :
320 : } // namespace block_graph
|