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/pe/block_util.h"
16 :
17 : #include "gtest/gtest.h"
18 :
19 : namespace pe {
20 :
21 : namespace {
22 :
23 : typedef block_graph::BlockGraph BlockGraph;
24 :
25 : class BlockUtilTest: public testing::Test {
26 : public:
27 E : virtual void SetUp() OVERRIDE {
28 E : }
29 :
30 : enum ReferenceSource {
31 : kSelfCode,
32 : kSelfData,
33 : kCodeBlock,
34 : kDataBlock,
35 : };
36 :
37 : enum ReferenceTarget {
38 : kTopOfBlock,
39 : kInCode,
40 : kDataLabel,
41 : kInData
42 : };
43 :
44 : struct ReferrerConfiguration {
45 E : bool operator<(const ReferrerConfiguration& rhs) const {
46 E : if (ref_source < rhs.ref_source)
47 E : return true;
48 E : if (ref_source > rhs.ref_source)
49 E : return false;
50 E : if (ref_target < rhs.ref_target)
51 E : return true;
52 E : if (ref_target > rhs.ref_target)
53 E : return false;
54 E : if (ref_type < rhs.ref_type)
55 E : return true;
56 E : if (ref_type > rhs.ref_type)
57 E : return false;
58 E : if (ref_size < rhs.ref_size)
59 E : return true;
60 E : if (ref_size > rhs.ref_size)
61 E : return false;
62 E : if (ref_is_direct < rhs.ref_is_direct)
63 E : return true;
64 E : return false;
65 E : }
66 :
67 : ReferenceSource ref_source;
68 : ReferenceTarget ref_target;
69 : BlockGraph::ReferenceType ref_type;
70 : size_t ref_size;
71 : bool ref_is_direct;
72 : };
73 :
74 : void TestCodeBlockReferrersAreClConsistent(
75 : const ReferrerConfiguration& config,
76 E : bool expect_valid) {
77 E : BlockGraph::Block* dst = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "s");
78 :
79 E : BlockGraph::Offset src_offset = 0;
80 :
81 : // Get the source block and source offset.
82 E : BlockGraph::Block* src = NULL;
83 E : switch (config.ref_source) {
84 : case kSelfCode:
85 E : src = dst;
86 E : src_offset = 4;
87 E : break;
88 :
89 : case kSelfData:
90 E : src = dst;
91 E : src_offset = 24;
92 E : break;
93 :
94 : case kCodeBlock:
95 E : src = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c");
96 E : src_offset = 4;
97 E : break;
98 :
99 : case kDataBlock:
100 E : src = image_.AddBlock(BlockGraph::DATA_BLOCK, 40, "d");
101 E : src_offset = 4;
102 : break;
103 : }
104 :
105 : // Set up a data label in the destination block, which splits it in half.
106 E : ASSERT_TRUE(dst->SetLabel(20, BlockGraph::Label(
107 : "data", BlockGraph::DATA_LABEL)));
108 :
109 : // We need the data label to be self-referenced otherwise the referrers test
110 : // will always fail. This is from a different offset than what we would
111 : // ever use for src_offset (4 or 24).
112 E : ASSERT_TRUE(dst->SetReference(16,
113 : BlockGraph::Reference(BlockGraph::ABSOLUTE_REF, 4, dst, 20, 20)));
114 :
115 : // These are reference offsets in dst as a function of ref_target.
116 E : const BlockGraph::Offset kRefOffsets[] = { 0, 10, 20, 30 };
117 :
118 : // Create the offset and the reference.
119 E : BlockGraph::Offset ref_offset = kRefOffsets[config.ref_target];
120 E : BlockGraph::Offset ref_base = ref_offset;
121 E : if (!config.ref_is_direct)
122 E : ref_base += 4;
123 :
124 : // Create the reference.
125 : BlockGraph::Reference ref(config.ref_type, config.ref_size, dst, ref_offset,
126 E : ref_base);
127 E : ASSERT_TRUE(ref.IsValid());
128 E : ASSERT_EQ(config.ref_is_direct, ref.IsDirect());
129 :
130 : // Hook it up.
131 E : ASSERT_TRUE(src->SetReference(src_offset, ref));
132 :
133 : // Test the validity.
134 E : ASSERT_EQ(expect_valid, CodeBlockReferrersAreClConsistent(dst));
135 E : }
136 :
137 : protected:
138 : BlockGraph image_;
139 : };
140 :
141 : } // namespace
142 :
143 E : TEST_F(BlockUtilTest, DirectReferencesFromCodeAreClConsistent) {
144 E : BlockGraph::Block* code1 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c1");
145 E : BlockGraph::Block* code2 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c2");
146 E : BlockGraph::Block* data1 = image_.AddBlock(BlockGraph::DATA_BLOCK, 40, "d1");
147 :
148 : // Direct code reference.
149 : EXPECT_TRUE(code1->SetReference(
150 E : 0, BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, code2, 0, 0)));
151 :
152 : // Direct data reference.
153 : EXPECT_TRUE(code1->SetReference(
154 E : 4, BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, data1, 0, 0)));
155 :
156 : // Direct self-reference.
157 : EXPECT_TRUE(code1->SetReference(
158 E : 8, BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, code1, 4, 4)));
159 :
160 E : EXPECT_TRUE(CodeBlockReferencesAreClConsistent(code1));
161 E : }
162 :
163 E : TEST_F(BlockUtilTest, IndirectReferencesFromCodeToCodeAreNotClConsistent) {
164 E : BlockGraph::Block* code1 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c1");
165 E : BlockGraph::Block* code2 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c2");
166 :
167 : // Indirect code reference.
168 : EXPECT_TRUE(code1->SetReference(
169 E : 0, BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, code2, 0, 4)));
170 :
171 E : EXPECT_FALSE(CodeBlockReferencesAreClConsistent(code1));
172 E : }
173 :
174 E : TEST_F(BlockUtilTest, IndirectReferencesFromCodeToDataAreClConsistent) {
175 E : BlockGraph::Block* code1 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c1");
176 E : BlockGraph::Block* data1 = image_.AddBlock(BlockGraph::DATA_BLOCK, 40, "d1");
177 :
178 : // Indirect data reference.
179 : EXPECT_TRUE(code1->SetReference(
180 E : 0, BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, data1, 0, 4)));
181 :
182 E : EXPECT_TRUE(CodeBlockReferencesAreClConsistent(code1));
183 E : }
184 :
185 E : TEST_F(BlockUtilTest, IndirectSelfReferencesFromCodeAreNotClConsistent) {
186 E : BlockGraph::Block* code1 = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c1");
187 :
188 : // Indirect self reference.
189 : EXPECT_TRUE(code1->SetReference(
190 E : 0, BlockGraph::Reference(BlockGraph::RELATIVE_REF, 4, code1, 4, 8)));
191 :
192 E : EXPECT_FALSE(CodeBlockReferencesAreClConsistent(code1));
193 E : }
194 :
195 E : TEST_F(BlockUtilTest, CodeBlockReferrersAreClConsistent) {
196 : // These are all the possible input values to be explored.
197 : const ReferenceSource kRefSource[] = {
198 E : kSelfCode, kSelfData, kCodeBlock, kDataBlock };
199 : const ReferenceTarget kRefTarget[] = {
200 E : kTopOfBlock, kInCode, kDataLabel, kInData };
201 : const BlockGraph::ReferenceType kRefType[] = {
202 E : BlockGraph::PC_RELATIVE_REF, BlockGraph::ABSOLUTE_REF,
203 E : BlockGraph::RELATIVE_REF, BlockGraph::FILE_OFFSET_REF };
204 E : const size_t kRefSize[] = { 1, 4 };
205 E : const bool kRefIsDirect[] = { false, true };
206 :
207 : static size_t kNumberOfPermutations =
208 : arraysize(kRefSource) * arraysize(kRefTarget) * arraysize(kRefType) *
209 : arraysize(kRefSize) * arraysize(kRefIsDirect);
210 :
211 : // This is the short list of permutations that we expect to be valid. All
212 : // others should be false.
213 : const ReferrerConfiguration kValidConfigs[] = {
214 : // Self-references from code to code.
215 E : { kSelfCode, kTopOfBlock, BlockGraph::PC_RELATIVE_REF, 1, true },
216 E : { kSelfCode, kTopOfBlock, BlockGraph::PC_RELATIVE_REF, 4, true },
217 E : { kSelfCode, kTopOfBlock, BlockGraph::ABSOLUTE_REF, 4, true },
218 E : { kSelfCode, kInCode, BlockGraph::PC_RELATIVE_REF, 1, true },
219 E : { kSelfCode, kInCode, BlockGraph::PC_RELATIVE_REF, 4, true },
220 E : { kSelfCode, kInCode, BlockGraph::ABSOLUTE_REF, 4, true },
221 :
222 : // Self-references from code to data.
223 E : { kSelfCode, kDataLabel, BlockGraph::ABSOLUTE_REF, 4, true },
224 :
225 : // Self-references from data to code.
226 E : { kSelfData, kTopOfBlock, BlockGraph::ABSOLUTE_REF, 4, true },
227 E : { kSelfData, kInCode, BlockGraph::ABSOLUTE_REF, 4, true },
228 :
229 : // Self-references from data to data.
230 E : { kSelfData, kDataLabel, BlockGraph::ABSOLUTE_REF, 4, true },
231 E : { kSelfData, kInData, BlockGraph::ABSOLUTE_REF, 4, true },
232 :
233 : // External references from code to code.
234 E : { kCodeBlock, kTopOfBlock, BlockGraph::PC_RELATIVE_REF, 4, true },
235 E : { kCodeBlock, kTopOfBlock, BlockGraph::ABSOLUTE_REF, 4, true },
236 :
237 : // External references from data to code.
238 E : { kDataBlock, kTopOfBlock, BlockGraph::ABSOLUTE_REF, 4, true },
239 E : { kDataBlock, kTopOfBlock, BlockGraph::RELATIVE_REF, 4, true },
240 : };
241 E : std::set<ReferrerConfiguration> valid_configs;
242 E : for (size_t i = 0; i < arraysize(kValidConfigs); ++i) {
243 E : ASSERT_TRUE(valid_configs.insert(kValidConfigs[i]).second);
244 E : }
245 :
246 : // Walk through all possible permutations.
247 E : for (size_t i = 0; i < kNumberOfPermutations; ++i) {
248 E : size_t j = i;
249 :
250 E : ReferenceSource ref_source = kRefSource[j % arraysize(kRefSource)];
251 E : j /= arraysize(kRefSource);
252 :
253 E : ReferenceTarget ref_target = kRefTarget[j % arraysize(kRefTarget)];
254 E : j /= arraysize(kRefTarget);
255 :
256 E : BlockGraph::ReferenceType ref_type = kRefType[j % arraysize(kRefType)];
257 E : j /= arraysize(kRefType);
258 :
259 E : size_t ref_size = kRefSize[j % arraysize(kRefSize)];
260 E : j /= arraysize(kRefSize);
261 :
262 E : bool ref_is_direct = kRefIsDirect[j % arraysize(kRefIsDirect)];
263 :
264 : // If the reference type and size is not valid, skip this test.
265 E : if (!BlockGraph::Reference::IsValidTypeSize(ref_type, ref_size))
266 E : continue;
267 :
268 E : ReferrerConfiguration config = { ref_source, ref_target, ref_type,
269 E : ref_size, ref_is_direct };
270 :
271 E : bool expect_valid = valid_configs.count(config);
272 : ASSERT_NO_FATAL_FAILURE(TestCodeBlockReferrersAreClConsistent(
273 E : config, expect_valid));
274 E : }
275 E : }
276 :
277 E : TEST_F(BlockUtilTest, CodeBlockReferrersAreClConsistentUnreferencedLabels) {
278 E : BlockGraph::Block* code = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c");
279 E : const BlockGraph::Offset kDataLabelOffset = 0x10;
280 : code->SetLabel(kDataLabelOffset,
281 E : BlockGraph::Label("data", BlockGraph::DATA_LABEL));
282 :
283 : // We have a single unreferenced data label.
284 E : ASSERT_FALSE(CodeBlockReferrersAreClConsistent(code));
285 :
286 : BlockGraph::Reference ref(BlockGraph::ABSOLUTE_REF,
287 : sizeof(core::AbsoluteAddress),
288 : code,
289 : kDataLabelOffset,
290 E : kDataLabelOffset);
291 : // Add a reference from code to the data label.
292 E : code->SetReference(kDataLabelOffset - 0x8, ref);
293 :
294 : // We're now consistent.
295 E : ASSERT_TRUE(CodeBlockReferrersAreClConsistent(code));
296 :
297 : // Remove the reference and move it into code.
298 E : code->RemoveReference(kDataLabelOffset - 0x8);
299 E : code->SetReference(kDataLabelOffset + 0x8, ref);
300 :
301 : // Consistent again.
302 E : ASSERT_TRUE(CodeBlockReferrersAreClConsistent(code));
303 E : }
304 :
305 E : TEST_F(BlockUtilTest, CodeBlockReferrersAreClConsistentUnreferencedData) {
306 E : BlockGraph::Block* code = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c");
307 : ASSERT_TRUE(code->SetLabel(20, BlockGraph::Label(
308 E : "data", BlockGraph::DATA_LABEL)));
309 E : ASSERT_FALSE(CodeBlockReferrersAreClConsistent(code));
310 E : }
311 :
312 E : TEST_F(BlockUtilTest, CodeBlockReferrersAreClConsistentCodeAfterData) {
313 : // We make a code block with a data label. We make sure the data label
314 : // is referenced. We expect this to fail because the data comes before the
315 : // code, which is not consistent with CL.EXE output.
316 E : BlockGraph::Block* code = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c");
317 : ASSERT_TRUE(code->SetLabel(0, BlockGraph::Label(
318 E : "data", BlockGraph::DATA_LABEL)));
319 : ASSERT_TRUE(code->SetLabel(20, BlockGraph::Label(
320 E : "code", BlockGraph::CODE_LABEL)));
321 : ASSERT_TRUE(code->SetReference(20, BlockGraph::Reference(
322 E : BlockGraph::ABSOLUTE_REF, 4, code, 0, 0)));
323 E : ASSERT_FALSE(CodeBlockReferrersAreClConsistent(code));
324 E : }
325 :
326 E : TEST_F(BlockUtilTest, CodeBlockIsClConsistent) {
327 : // Each of the sub-functions has been tested in detail, so we simply do an
328 : // end-to-end test for coverage.
329 E : BlockGraph::Block* code = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c");
330 E : ASSERT_TRUE(CodeBlockIsClConsistent(code));
331 :
332 : ASSERT_TRUE(code->SetLabel(20, BlockGraph::Label(
333 E : "data", BlockGraph::DATA_LABEL)));
334 E : ASSERT_FALSE(CodeBlockIsClConsistent(code));
335 :
336 : ASSERT_TRUE(code->SetReference(8, BlockGraph::Reference(
337 E : BlockGraph::PC_RELATIVE_REF, 1, code, 0, 0)));
338 E : ASSERT_FALSE(CodeBlockIsClConsistent(code));
339 :
340 : ASSERT_TRUE(code->SetReference(4, BlockGraph::Reference(
341 E : BlockGraph::ABSOLUTE_REF, 4, code, 20, 20)));
342 E : ASSERT_TRUE(CodeBlockIsClConsistent(code));
343 E : }
344 :
345 E : TEST_F(BlockUtilTest, CodeBlockIsBasicBlockDecomposableSimpleBlock) {
346 E : BlockGraph::Block* code = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c");
347 E : ASSERT_TRUE(CodeBlockIsClConsistent(code));
348 E : }
349 :
350 E : TEST_F(BlockUtilTest, CodeBlockIsBasicBlockDecomposableBuiltBySyzygy) {
351 E : BlockGraph::Block* code = image_.AddBlock(BlockGraph::CODE_BLOCK, 40, "c");
352 E : code->set_attribute(BlockGraph::BUILT_BY_SYZYGY);
353 E : ASSERT_TRUE(CodeBlockIsBasicBlockDecomposable(code));
354 :
355 : // Even if this block has unreferenced data, it should be fine.
356 : ASSERT_TRUE(code->SetLabel(20, BlockGraph::Label(
357 E : "data", BlockGraph::DATA_LABEL)));
358 E : ASSERT_TRUE(CodeBlockIsBasicBlockDecomposable(code));
359 E : }
360 :
361 : } // namespace pe
|