Implement ERM

4 files changed, 175 insertions, 75 deletions

diff --git a/README.md b/README.md
index 7a91a02..682632d 100644
--- a/README.md
+++ b/README.md
@@ -16,7 +16,7 @@ To install taosc to `$prefix`, you'll also need `install(1p)`:
 
 ## Usage
 
-    taosc-fix WORKDIR TIMEOUT EXECUTABLE PROOFS-OF-CONCEPT [OPTION]...
+    taosc-fix WORKDIR TIMEOUT EXECUTABLE PROOFS_OF_CONCEPT [OPTION]...
 
 ## Copying
 
diff --git a/Variables.zig b/Variables.zig
new file mode 100644
index 0000000..c4c40de
--- /dev/null
+++ b/Variables.zig
@@ -0,0 +1,121 @@
+//! Variables captured at patch location
+// Copyright (C) 2025  Nguyễn Gia Phong
+//
+// This file is part of taosc.
+//
+// Taosc is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Affero General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// Taosc is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU Affero General Public License for more details.
+//
+// You should have received a copy of the GNU Affero General Public License
+// along with taosc.  If not, see <https://www.gnu.org/licenses/>.
+
+const Allocator = std.mem.Allocator;
+const Writer = std.io.Writer;
+const assert = std.debug.assert;
+const bytesAsSlice = std.mem.bytesAsSlice;
+const cwd = std.fs.cwd;
+const divCeil = std.math.divCeil;
+const fields = std.meta.fields;
+const std = @import("std");
+const suggestVectorLength = std.simd.suggestVectorLength;
+
+pub const RegisterEnum = enum(u5) { // TODO: u4
+    rflags, // TODO: remove
+    r15, r14, r13, r12, r11, r10, r9, r8,
+    rdi, rsi, rbp, rbx, rdx, rcx, rax,
+    rsp, // TODO: remove
+    rip, // TODO: remove
+
+    pub fn format(tag: RegisterEnum, writer: *Writer) Writer.Error!void {
+        try writer.print("{s}", .{ @tagName(tag) });
+    }
+};
+const Register = i64;
+const Registers = [fields(RegisterEnum).len]Register;
+
+pub const signed_integers = .{ i64, i32, i16, i8 };
+const len = suggestVectorLength(Register).?;
+const alignment = @alignOf(@Vector(len, Register));
+comptime {
+    for (signed_integers) |Int| {
+        assert(alignment == @alignOf(@Vector(len, Int)));
+        assert(alignment % @sizeOf(Int) == 0);
+    }
+}
+
+fn alignedSize(T: type, count: usize) !usize {
+    return try divCeil(usize, @sizeOf(T) * count, alignment) * alignment;
+}
+
+fn packedSize(T: type, container_size: usize, count: usize) !usize {
+    return @divExact(container_size, @sizeOf(T)) * try alignedSize(T, count);
+}
+
+const Variables = @This();
+bytes: []align(alignment) const u8,
+samples: usize,
+
+pub fn init(allocator: Allocator, stack_size: usize,
+            path: []const u8) !Variables {
+    var dir = try cwd().openDir(path, .{ .iterate = true });
+    defer dir.close();
+    var entries = dir.iterate();
+    var count: usize = 0;
+    while (try entries.next()) |entry| {
+        assert(entry.kind == .file);
+        count += 1;
+    }
+    var size = try packedSize(Register, @sizeOf(Registers), count);
+    inline for (signed_integers) |Int|
+        size += try packedSize(Int, stack_size, count);
+    const bytes = try allocator.alignedAlloc(u8,
+        .fromByteUnits(alignment), size);
+    errdefer allocator.free(bytes);
+
+    const file_size = @sizeOf(Registers) + stack_size;
+    const buffer = try allocator.alignedAlloc(u8,
+        .fromByteUnits(@alignOf(Registers)), file_size);
+    defer allocator.free(buffer);
+    const registers: *Registers = @ptrCast(buffer.ptr);
+    entries.reset();
+    for (0..count) |index| {
+        const entry = try entries.next();
+        const file = try dir.openFile(entry.?.name, .{});
+        defer file.close();
+        assert(try file.getEndPos() == file_size);
+        assert(try file.read(buffer) == file_size);
+        var offset: usize = 0;
+        inline for (registers) |reg| {
+            const slice = bytesAsSlice(Register, bytes[offset..]);
+            slice[index] = reg;
+            offset += try alignedSize(Register, count);
+        }
+        inline for (signed_integers) |Int| {
+            const aligned_size = try alignedSize(Int, count);
+            for (bytesAsSlice(Int, buffer[@sizeOf(Registers)..])) |value| {
+                const slice = bytesAsSlice(Int, bytes[offset..]);
+                slice[index] = value;
+                offset += aligned_size;
+            }
+        }
+    }
+    return .{ .bytes = bytes, .samples = count };
+}
+
+pub fn deinit(variables: Variables, allocator: Allocator) void {
+    allocator.free(variables.bytes);
+}
+
+pub fn register(variables: Variables, name: RegisterEnum) ![]const Register {
+    const aligned_size = try alignedSize(Register, variables.samples);
+    const offset = aligned_size * @intFromEnum(name);
+    const slice = bytesAsSlice(Register, variables.bytes[offset..]);
+    return @alignCast(slice[0..variables.samples]);
+}
diff --git a/fix.m4 b/fix.m4
index 3425e53..4ae99b9 100644
--- a/fix.m4
+++ b/fix.m4
@@ -33,7 +33,7 @@ bad() {
 
 if test $# -lt 4
 then
-  echo Usage: taosc-fix WORKDIR TIMEOUT EXECUTABLE PROOFS-OF-CONCEPT [OPTION]...
+  echo Usage: taosc-fix WORKDIR TIMEOUT EXECUTABLE PROOFS_OF_CONCEPT [OPTION]...
   exit 1
 fi
 wd="$(realpath $1)"
@@ -135,4 +135,6 @@ do
       "$bin.collect" $options "$input"
   done
 done
+# TODO: split if the patch location is reached multiple times with an input
+taosc-synth $stack_size "$wd"/values/{benign,malicious} > "$wd/predicates"
 # vim: filetype=sh.m4
diff --git a/synth.zig b/synth.zig
index 453cb46..4e74cd8 100644
--- a/synth.zig
+++ b/synth.zig
@@ -16,83 +16,54 @@
 // You should have received a copy of the GNU Affero General Public License
 // along with taosc.  If not, see <https://www.gnu.org/licenses/>.
 
-const Allocator = std.mem.Allocator;
 const ArenaAllocator = std.heap.ArenaAllocator;
-const Dir = std.fs.Dir;
-const File = std.fs.File;
-const Reader = std.Io.Reader;
+const CompareOperator = std.math.CompareOperator;
+const Writer = std.io.Writer;
 const argsAlloc = std.process.argsAlloc;
 const argsFree = std.process.argsFree;
 const assert = std.debug.assert;
-const cwd = std.fs.cwd;
+const compare = std.math.compare;
+const enums = std.enums;
 const exit = std.process.exit;
 const page_allocator = std.heap.page_allocator;
 const parseUnsigned = std.fmt.parseUnsigned;
 const print = std.debug.print;
 const std = @import("std");
 
-const State = extern struct {
-    flags: u16,
-    r15: i64,
-    r14: i64,
-    r13: i64,
-    r12: i64,
-    r11: i64,
-    r10: i64,
-    r9: i64,
-    r8: i64,
-    rdi: i64,
-    rsi: i64,
-    rbp: i64,
-    rbx: i64,
-    rdx: i64,
-    rcx: i64,
-    rax: i64,
-    rsp: u64, // internal use only
-    rip: i64,
-};
-
-fn countFiles(dir: Dir) Dir.Iterator.Error!usize {
-    var count: usize = 0;
-    var entries = dir.iterate();
-    while (try entries.next()) |entry| {
-        assert(entry.kind == .file);
-        count += 1;
-    }
-    return count;
-}
-
-const ReadError = Dir.Iterator.Error || File.OpenError || Reader.Error;
+const RegisterEnum = Variables.RegisterEnum;
+const Variables = @import("Variables.zig");
+const signed_integers = Variables.signed_integers;
 
-const Data = struct {
-    states: []const State,
-    memory: []const u8,
+const Variable = RegisterEnum;
+const Expression = Variable;
+const Comparison = struct {
+    lhs: Expression,
+    op: CompareOperator,
+    rhs: Expression,
 
-    fn init(allocator: Allocator, dir: Dir,
-            stack_len: u64) (Allocator.Error || ReadError)!Data {
-        const count = try countFiles(dir);
-        const states = try allocator.alloc(State, count);
-        const memory = try allocator.alloc(u8, stack_len * count);
-        var entries = dir.iterate();
-        var sp: u64 = 0;
-        for (states) |*state| {
-            const entry = try entries.next();
-            const file = try dir.openFile(entry.?.name, .{});
-            defer file.close();
-            var buffer: [4096]u8 = undefined;
-            var reader = file.reader(&buffer);
-            assert(try reader.read(@ptrCast(state)) == @sizeOf(State));
-            state.rsp = sp;
-            assert(try reader.read(memory[sp..][0..stack_len]) == stack_len);
-            sp += stack_len;
-            print("{}\n", .{ state });
-        }
-        return .{ .states = states, .memory = memory };
+    fn check(cmp: Comparison, bot: Variables, top: Variables) !bool {
+        for (try bot.register(cmp.lhs), try bot.register(cmp.rhs)) |lhs, rhs|
+            if (compare(lhs, cmp.op, rhs))
+                return false;
+        for (try top.register(cmp.lhs), try top.register(cmp.rhs)) |lhs, rhs|
+            if (!compare(lhs, cmp.op, rhs))
+                return false;
+        return true;
     }
 
-    fn deinit(data: Data, allocator: Allocator) void {
-        allocator.free(data.states);
-        allocator.free(data.memory);
+    pub fn format(cmp: Comparison, writer: *Writer) Writer.Error!void {
+        try writer.print("{s}{f}{f}", .{
+            switch (cmp.op) {
+                .lt => "<",
+                .lte => "<=",
+                .eq => "==",
+                .gte => ">=",
+                .gt => ">",
+                .neq => "!=",
+            },
+            cmp.lhs,
+            cmp.rhs,
+        });
     }
 };
 
@@ -103,17 +74,23 @@ pub fn main() !void {
     const args = try argsAlloc(allocator);
     defer argsFree(allocator, args);
     if (args.len != 4) {
-        print("Usage: taosc-synth OFF-DIR ON-DIR STACK-SIZE", .{});
+        print("Usage: taosc-synth STACK_SIZE BOTTOM_DIR TOP_DIR", .{});
         exit(1);
     }
-    var off_dir = try cwd().openDir(args[1], .{ .iterate = true });
-    defer off_dir.close();
-    var on_dir = try cwd().openDir(args[2], .{ .iterate = true });
-    defer on_dir.close();
-    const stack_len = try parseUnsigned(u64, args[3], 0);
+    const stack_size = try parseUnsigned(usize, args[1], 0);
+    inline for (signed_integers) |Int|
+        assert(stack_size % @sizeOf(Int) == 0);
+    const bot = try Variables.init(allocator, stack_size, args[2]);
+    defer bot.deinit(allocator);
+    const top = try Variables.init(allocator, stack_size, args[3]);
+    defer top.deinit(allocator);
 
-    const off_data = try Data.init(allocator, off_dir, stack_len);
-    defer off_data.deinit(allocator);
-    const on_data = try Data.init(allocator, on_dir, stack_len);
-    defer on_data.deinit(allocator);
+    for (enums.values(RegisterEnum)) |lhs|
+        for (enums.values(RegisterEnum)) |rhs|
+            if (@intFromEnum(lhs) < @intFromEnum(rhs))
+                for (enums.values(CompareOperator)) |op| {
+                    const cmp = Comparison{ .lhs = lhs, .op = op, .rhs = rhs };
+                    if (try cmp.check(bot, top))
+                        print("{f}\n", .{ cmp });
+                };
 }