lib/closure/src/link/cover.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const binary = @import("../binary/root.zig");
2 const std = @import("std");
3
4 pub const attributions_max: usize = 64;
5 pub const padding_ranges_max: usize = 64;
6
7 pub const Kind = enum(u8) {
8 root,
9 primitive,
10 };
11
12 pub const Attribution = struct {
13 kind: Kind,
14 offset: u64,
15 address: u64,
16 length: u64,
17 source_offset: u64 = 0,
18 relocation_count: u32 = 0,
19 source_sha256: [32]u8,
20 };
21
22 pub const Padding = struct {
23 offset: u64,
24 address: u64,
25 length: u16,
26 };
27
28 pub const Policy = struct {
29 padding_bytes_max: u16 = 15,
30 padding_byte: u8 = 0xcc,
31 };
32
33 pub const Scratch = struct {
34 ordered: []Attribution,
35 padding: []Padding,
36 };
37
38 pub const Report = struct {
39 attributions: []const Attribution,
40 padding: []const Padding,
41 root_bytes: u64,
42 primitive_bytes: u64,
43 padding_bytes: u64,
44 executable_bytes: u64,
45 executable_sha256: [32]u8,
46 work: u64,
47 };
48
49 const CoverError = error{
50 AttributionCapacityExceeded,
51 AttributionDigestMissing,
52 AttributionOutsideExecutable,
53 AttributionOverlap,
54 ExecutableCoverageMissing,
55 PaddingCapacityExceeded,
56 PaddingInvalid,
57 };
58
59 pub const Error = binary.strict.Error || CoverError;
60
61 pub fn verify(
62 bytes: []const u8,
63 image: binary.strict.Report,
64 input: []const Attribution,
65 policy: Policy,
66 scratch: Scratch,
67 ) Error!Report {
68 if (input.len > scratch.ordered.len or
69 input.len > attributions_max or
70 scratch.padding.len > padding_ranges_max)
71 {
72 return error.AttributionCapacityExceeded;
73 }
74 @memcpy(scratch.ordered[0..input.len], input);
75 const ordered = scratch.ordered[0..input.len];
76 sort(ordered);
77 var work: u64 = input.len;
78 try validateAttributions(image, ordered, &work);
79 var padding_count: usize = 0;
80 var root_bytes: u64 = 0;
81 var primitive_bytes: u64 = 0;
82 var padding_bytes: u64 = 0;
83 var executable_bytes: u64 = 0;
84 var attributed_count: usize = 0;
85 var hasher = std.crypto.hash.sha2.Sha256.init(.{});
86 for (image.loads) |load| {
87 if (!load.executable) continue;
88 const start = toOffset(load.offset) catch
89 return error.AttributionOutsideExecutable;
90 const length = toOffset(load.content_bytes) catch
91 return error.AttributionOutsideExecutable;
92 const contents = try take(bytes, start, length);
93 hasher.update(contents);
94 executable_bytes = try added(executable_bytes, load.content_bytes);
95 var cursor = load.offset;
96 const end = try added(load.offset, load.content_bytes);
97 for (ordered) |attribution| {
98 work += 1;
99 if (attribution.offset < load.offset or
100 attribution.offset >= end)
101 {
102 continue;
103 }
104 const gap = attribution.offset - cursor;
105 if (gap != 0) {
106 try appendPadding(
107 bytes,
108 load,
109 cursor,
110 gap,
111 policy,
112 scratch.padding,
113 &padding_count,
114 &padding_bytes,
115 &work,
116 );
117 }
118 switch (attribution.kind) {
119 .root => root_bytes =
120 try added(root_bytes, attribution.length),
121 .primitive => primitive_bytes =
122 try added(primitive_bytes, attribution.length),
123 }
124 cursor = try added(attribution.offset, attribution.length);
125 attributed_count += 1;
126 }
127 if (cursor < end) {
128 try appendPadding(
129 bytes,
130 load,
131 cursor,
132 end - cursor,
133 policy,
134 scratch.padding,
135 &padding_count,
136 &padding_bytes,
137 &work,
138 );
139 }
140 if (cursor > end) return error.AttributionOverlap;
141 }
142 if (attributed_count != ordered.len) {
143 return error.AttributionOutsideExecutable;
144 }
145 const accounted = try added(
146 try added(root_bytes, primitive_bytes),
147 padding_bytes,
148 );
149 if (accounted != executable_bytes) {
150 return error.ExecutableCoverageMissing;
151 }
152 var digest: [32]u8 = undefined;
153 hasher.final(&digest);
154 return .{
155 .attributions = ordered,
156 .padding = scratch.padding[0..padding_count],
157 .root_bytes = root_bytes,
158 .primitive_bytes = primitive_bytes,
159 .padding_bytes = padding_bytes,
160 .executable_bytes = executable_bytes,
161 .executable_sha256 = digest,
162 .work = work,
163 };
164 }
165
166 fn validateAttributions(
167 image: binary.strict.Report,
168 ordered: []const Attribution,
169 work: *u64,
170 ) Error!void {
171 var previous_end: u64 = 0;
172 for (ordered, 0..) |attribution, index| {
173 work.* += 1;
174 if (attribution.length == 0 or
175 !digestKnown(attribution.source_sha256))
176 {
177 return error.AttributionDigestMissing;
178 }
179 if (index != 0 and attribution.offset < previous_end) {
180 return error.AttributionOverlap;
181 }
182 const end = try added(attribution.offset, attribution.length);
183 var admitted = false;
184 for (image.loads) |load| {
185 work.* += 1;
186 if (!load.executable) continue;
187 const load_end = try added(load.offset, load.content_bytes);
188 if (attribution.offset < load.offset or end > load_end) continue;
189 const relative = attribution.offset - load.offset;
190 if (attribution.address != try added(load.address, relative)) {
191 return error.AttributionOutsideExecutable;
192 }
193 admitted = true;
194 break;
195 }
196 if (!admitted) return error.AttributionOutsideExecutable;
197 previous_end = end;
198 }
199 }
200
201 fn appendPadding(
202 bytes: []const u8,
203 load: binary.strict.Load,
204 offset: u64,
205 length: u64,
206 policy: Policy,
207 output: []Padding,
208 count: *usize,
209 total: *u64,
210 work: *u64,
211 ) Error!void {
212 if (length == 0 or length > policy.padding_bytes_max) {
213 return error.PaddingInvalid;
214 }
215 if (count.* == output.len) return error.PaddingCapacityExceeded;
216 const start = toOffset(offset) catch return error.PaddingInvalid;
217 const length_usize = toOffset(length) catch return error.PaddingInvalid;
218 const contents = try take(bytes, start, length_usize);
219 for (contents) |byte| {
220 work.* += 1;
221 if (byte != policy.padding_byte) return error.PaddingInvalid;
222 }
223 output[count.*] = .{
224 .offset = offset,
225 .address = try added(load.address, offset - load.offset),
226 .length = @intCast(length),
227 };
228 count.* += 1;
229 total.* = try added(total.*, length);
230 }
231
232 fn sort(values: []Attribution) void {
233 var index: usize = 1;
234 while (index < values.len) : (index += 1) {
235 const value = values[index];
236 var cursor = index;
237 while (cursor > 0 and values[cursor - 1].offset > value.offset) {
238 values[cursor] = values[cursor - 1];
239 cursor -= 1;
240 }
241 values[cursor] = value;
242 }
243 }
244
245 fn digestKnown(digest: [32]u8) bool {
246 for (digest) |byte| {
247 if (byte != 0) return true;
248 }
249 return false;
250 }
251
252 fn take(
253 bytes: []const u8,
254 offset: usize,
255 length: usize,
256 ) Error![]const u8 {
257 const end = std.math.add(usize, offset, length) catch
258 return error.BinaryArithmeticOverflow;
259 if (end > bytes.len) return error.TruncatedBinary;
260 return bytes[offset..end];
261 }
262
263 fn toOffset(value: u64) Error!usize {
264 return std.math.cast(usize, value) orelse
265 error.BinaryArithmeticOverflow;
266 }
267
268 fn added(left: anytype, right: anytype) Error!u64 {
269 return std.math.add(
270 u64,
271 @intCast(left),
272 @intCast(right),
273 ) catch error.BinaryArithmeticOverflow;
274 }
275
276 test "coverage attributes every executable byte with bounded padding" {
277 var bytes: [32]u8 = @splat(0);
278 @memset(bytes[4..8], 0x11);
279 @memset(bytes[8..11], 0xcc);
280 @memset(bytes[11..15], 0x22);
281 const loads = [_]binary.strict.Load{.{
282 .offset = 4,
283 .address = 0x1000,
284 .file_bytes = 16,
285 .content_bytes = 11,
286 .memory_bytes = 16,
287 .readable = true,
288 .writable = false,
289 .executable = true,
290 }};
291 const image = binary.strict.Report{
292 .kind = .elf64,
293 .loads = &loads,
294 .relocations = &.{},
295 .executable_bytes = 11,
296 .initialized_bytes = 0,
297 .memory_bytes = 16,
298 .stack_bytes = 0,
299 .timestamp = 0,
300 .image_base = 0,
301 .work = 1,
302 };
303 const digest: [32]u8 = @splat(1);
304 const input = [_]Attribution{
305 .{
306 .kind = .primitive,
307 .offset = 11,
308 .address = 0x1007,
309 .length = 4,
310 .source_sha256 = digest,
311 },
312 .{
313 .kind = .root,
314 .offset = 4,
315 .address = 0x1000,
316 .length = 4,
317 .source_sha256 = digest,
318 },
319 };
320 var ordered: [2]Attribution = undefined;
321 var padding: [1]Padding = undefined;
322 const report = try verify(
323 &bytes,
324 image,
325 &input,
326 .{},
327 .{ .ordered = &ordered, .padding = &padding },
328 );
329 try std.testing.expectEqual(@as(u64, 4), report.root_bytes);
330 try std.testing.expectEqual(@as(u64, 4), report.primitive_bytes);
331 try std.testing.expectEqual(@as(u64, 3), report.padding_bytes);
332 try std.testing.expectEqual(@as(u64, 11), report.executable_bytes);
333 }
334
335 test "coverage fails closed on foreign and excessive gaps" {
336 var bytes: [32]u8 = @splat(0xcc);
337 const loads = [_]binary.strict.Load{.{
338 .offset = 4,
339 .address = 0x1000,
340 .file_bytes = 16,
341 .content_bytes = 16,
342 .memory_bytes = 16,
343 .readable = true,
344 .writable = false,
345 .executable = true,
346 }};
347 const image = binary.strict.Report{
348 .kind = .elf64,
349 .loads = &loads,
350 .relocations = &.{},
351 .executable_bytes = 16,
352 .initialized_bytes = 0,
353 .memory_bytes = 16,
354 .stack_bytes = 0,
355 .timestamp = 0,
356 .image_base = 0,
357 .work = 1,
358 };
359 const digest: [32]u8 = @splat(1);
360 const input = [_]Attribution{.{
361 .kind = .root,
362 .offset = 4,
363 .address = 0x1000,
364 .length = 1,
365 .source_sha256 = digest,
366 }};
367 var ordered: [1]Attribution = undefined;
368 var padding: [1]Padding = undefined;
369 try std.testing.expectError(
370 error.PaddingInvalid,
371 verify(
372 &bytes,
373 image,
374 &input,
375 .{ .padding_bytes_max = 14 },
376 .{ .ordered = &ordered, .padding = &padding },
377 ),
378 );
379 bytes[5] = 0x90;
380 const full = [_]Attribution{.{
381 .kind = .root,
382 .offset = 6,
383 .address = 0x1002,
384 .length = 14,
385 .source_sha256 = digest,
386 }};
387 try std.testing.expectError(
388 error.PaddingInvalid,
389 verify(
390 &bytes,
391 image,
392 &full,
393 .{},
394 .{ .ordered = &ordered, .padding = &padding },
395 ),
396 );
397 }