commit e6ba0a8ba439af99443ca053df69b96a4ae16e23
parent 32a90ed1c2548dfe6e6bb9368fbf484bfd544cdf
Author: Jared Tobin <jared@jtobin.io>
Date: Wed, 21 Oct 2026 09:15:00 +0400
diff: a return is downstream, never an origin
A return goes where the call before it sent it. When control diverges
before a function is called, from one site in one run and another in
the next, the function's return takes its targets in other proportions
or another order, and diff reported it as a control origin, in the
callee, away from the branch that chose. On the Penumbra spike four or
five of each root's 23 to 27 control origins were `retq`.
The plugin now reads each instruction's bytes at translation and marks
the returns, x86_64's RET and aarch64's RET, RETAA, and RETAB, with an
R line. diff counts a return whose transfers differ as downstream,
whether or not it ran as often in every run, and never as an origin.
GHC returns to a continuation by an indirect jump, which is not marked
and stays an origin where its targets differ.
The probe harness gains a helper called from two sites the secret
chooses between; with the returns unmarked, the check fails on a
control origin in the helper.
Diffstat:
7 files changed, 126 insertions(+), 32 deletions(-)
diff --git a/CHANGELOG b/CHANGELOG
@@ -15,10 +15,11 @@
diverge (vestigia/diff-v3: each run with how it was made, each
origin with the runs alike there and the runs that never
reached it, a branch taking its outcomes in another order an
- origin too, and what ran downstream listed per object), set
- against controls repeating a secret, with what every run
- executed in each object, and runs designed to reach particular
- paths compared for control and coverage alone (`--designed`);
+ origin too, a return never one, and what ran downstream listed
+ per object), set against controls repeating a secret, with
+ what every run executed in each object, and runs designed to
+ reach particular paths compared for control and coverage alone
+ (`--designed`);
runs are recorded, an x86_64 or aarch64 harness on either
host, with randomisation off (or not at all) and the guest's
entropy, its getrandom included, seeded, and QEMU's own
diff --git a/README.md b/README.md
@@ -77,8 +77,9 @@ address 0x152c8 Fq::sqrt_ratio_zeta invsqrt.rs:113 ...
An *origin* is a branch whose outcomes differ between runs, in
proportion or in order, or an instruction whose addresses differ.
Each names the runs that behaved alike there. Instructions that
-merely ran a different number of times are listed as downstream, and
-every instruction some run executed is listed as coverage.
+merely ran a different number of times are listed as downstream, as
+are returns whose targets differ, which go where their calls sent
+them; and every instruction some run executed is listed as coverage.
* `--control DUMP` repeats the first run's secret; whatever differs
between the two is *unsteady* and kept out of the origins.
diff --git a/etc/probe/harness.c b/etc/probe/harness.c
@@ -6,8 +6,9 @@
* License: MIT
*
* Its secret, the first argument in hex (of one width for every
- * secret, so that runs lay out alike), reaches a loop's bound and a
- * table index; a constant-time select reaches neither.
+ * secret, so that runs lay out alike), reaches a loop's bound, a
+ * table index, and which of two calls a helper returns to; a
+ * constant-time select reaches none of them.
*/
#include <stdio.h>
#include <stdlib.h>
@@ -26,6 +27,21 @@ __attribute__((noinline)) unsigned lookup(unsigned s) {
return table[s & 0xff];
}
+__attribute__((noinline)) unsigned leaf(unsigned x) {
+ return x * 3u + 1u;
+}
+
+/* leaf runs eight times whatever the secret, but returns to one call
+ or the other as the secret's bits say */
+__attribute__((noinline)) unsigned calls(unsigned s) {
+ unsigned r = 0;
+ for (unsigned i = 0; i < 8; i++) {
+ if ((s >> i) & 1u) r += leaf(i);
+ else r ^= leaf(i + 1u);
+ }
+ return r;
+}
+
__attribute__((noinline)) unsigned ct(unsigned s, unsigned p) {
unsigned m = 0u - (p & 1u);
return (s & m) | (~s & ~m);
@@ -33,13 +49,14 @@ __attribute__((noinline)) unsigned ct(unsigned s, unsigned p) {
int main(int argc, char **argv) {
unsigned s = (unsigned)strtoul(argc > 1 ? argv[1] : "0", NULL, 16);
- unsigned out[3];
+ unsigned out[4];
for (int i = 0; i < 256; i++) table[i] = (unsigned char)i;
vestigia_secret(&s, sizeof s);
out[0] = branchy(s);
out[1] = lookup(s);
- out[2] = ct(s, 1);
+ out[2] = calls(s);
+ out[3] = ct(s, 1);
vestigia_public(out, sizeof out);
- printf("%u %u %u\n", out[0], out[1], out[2]);
+ printf("%u %u %u %u\n", out[0], out[1], out[2], out[3]);
return 0;
}
diff --git a/lib/Vestigia/Diff.hs b/lib/Vestigia/Diff.hs
@@ -23,7 +23,10 @@
-- An instruction run equally often in every run whose addresses
-- differ computed one from the secret: an `address` origin. Every
-- other instruction run a different number of times sits where
--- control had already diverged: it is downstream.
+-- control had already diverged: it is downstream. So is a return
+-- whose transfers differ, however often it ran: it goes where the
+-- call before it sent it, so its outcomes differ only because
+-- control had diverged before the call.
--
-- Unlike memcheck's taint, this sees what control flow does to
-- data as well as what data does: a value chosen by a secret
@@ -113,11 +116,12 @@ data Run = Run {
} deriving (Eq, Show)
-- | One run: its instructions by address, its transfers by source,
--- each a count per target, and how it was made, where its dump
--- says.
+-- each a count per target, the instructions that return, and how
+-- it was made, where its dump says.
data Dump = Dump {
dpInsns :: !(M.Map Integer Insn)
, dpTransfers :: !(M.Map Integer (M.Map Integer Integer))
+ , dpReturns :: !(S.Set Integer)
, dpRun :: !(Maybe Run)
} deriving (Eq, Show)
@@ -130,12 +134,12 @@ data Dump = Dump {
-- bytes, in hex; @X@, the exit status, in decimal) is read whole or
-- not at all.
readDump :: T.Text -> Either String Dump
-readDump t = go (T.lines t) M.empty M.empty [] Nothing Nothing
+readDump t = go (T.lines t) M.empty M.empty S.empty [] Nothing Nothing
where
- go ls is es as env st = case ls of
+ go ls is es rs as env st = case ls of
[]
| any ((> 0) . inCount) (M.elems is) ->
- Dump is es <$> record (reverse as) env st
+ Dump is es rs <$> record (reverse as) env st
| otherwise ->
Left "no instruction ran: the run was not recorded"
(l : rest) -> case T.words l of
@@ -144,27 +148,30 @@ readDump t = go (T.lines t) M.empty M.empty [] Nothing Nothing
<*> pure ord
<*> pure (if obj == "-" then Nothing else Just obj)
<*> unhex off
- go rest (M.insert (inPc i) i is) es as env st
+ go rest (M.insert (inPc i) i is) es rs as env st
[ "E", from, to, n ] -> do
f <- unhex from
k <- unhex to
c <- unhex n
go rest is (M.insertWith M.union f (M.singleton k c) es)
- as env st
+ rs as env st
+ [ "R", pc ] -> do
+ r <- unhex pc
+ go rest is es (S.insert r rs) as env st
[ "T", _ ] ->
Left "the guest started a second thread, which a trace \
\cannot record: the run was stopped"
- [ "A" ] -> go rest is es (BS.empty : as) env st
+ [ "A" ] -> go rest is es rs (BS.empty : as) env st
[ "A", h ] -> do
b <- unhexBytes h
- go rest is es (b : as) env st
+ go rest is es rs (b : as) env st
[ "N", n, b ] -> do
v <- (,) <$> unhex n <*> unhex b
- go rest is es as (Just v) st
+ go rest is es rs as (Just v) st
[ "X", x ] -> case readMaybe (T.unpack x) of
- Just v -> go rest is es as env (Just v)
+ Just v -> go rest is es rs as env (Just v)
Nothing -> Left ("not an exit status: " <> T.unpack x)
- [] -> go rest is es as env st
+ [] -> go rest is es rs as env st
_ -> Left ("an unreadable dump line: " <> T.unpack l)
record as env st = case (as, env, st) of
([], Nothing, Nothing) -> pure Nothing
@@ -373,9 +380,16 @@ diffDesigned cs ds xs = Divergence {
(r : rest) -> not (all (outcomesAlike r) rest)
[] -> False
- controlPcs = S.filter divergent transferSources
+ -- a return goes where its call sent it: downstream, never an
+ -- origin, whatever its outcomes
+ returns = S.unions (fmap dpReturns runs)
+ divergentPcs = S.filter divergent transferSources
+ controlPcs = divergentPcs `S.difference` returns
addressPcs = S.fromList [ inPc i | (_, i) <- addresses ]
- downstream = ((pcs `S.difference` steady) `S.difference` controlPcs)
+ downstream =
+ (((pcs `S.difference` steady)
+ `S.union` (divergentPcs `S.intersection` returns))
+ `S.difference` controlPcs)
`S.difference` addressPcs
controls =
diff --git a/nix/probe.nix b/nix/probe.nix
@@ -51,8 +51,10 @@ let
# each report's (class, function) pairs in the harness, sorted
expected = {
- trace = [ [ "address" "lookup" ] [ "control" "branchy" ] ];
- diff = [ [ "address" "lookup" ] [ "control" "branchy" ] ];
+ trace = [ [ "address" "lookup" ] [ "control" "branchy" ]
+ [ "control" "calls" ] ];
+ diff = [ [ "address" "lookup" ] [ "control" "branchy" ]
+ [ "control" "calls" ] ];
};
in
pkgs.runCommand "vestigia-probe-check" {
diff --git a/plugin/vestigia-qemu.c b/plugin/vestigia-qemu.c
@@ -16,12 +16,15 @@
* transfers as often in another order, and an instruction run as
* often but touching other addresses computed one from the secret.
* Nothing needs aligning, and no taint is propagated, so effects of
- * control flow are seen as well as those of data flow.
+ * control flow are seen as well as those of data flow. It marks the
+ * instructions that return (x86_64's and aarch64's), which go where
+ * the call before them sent them.
*
* At exit it writes, to the file named by its `out` argument:
*
* I <pc> <count> <accesses> <fingerprint> <order> <object> <address>
* E <from> <to> <count>
+ * R <pc>
*
* or, for a guest that started a second thread, the line `T 2` alone.
*
@@ -48,10 +51,14 @@
QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
+/* what an instruction is to a comparison, read from its bytes */
+enum { PLAIN, RETURN };
+
typedef struct Insn {
uint64_t pc;
uint64_t size;
uintptr_t haddr;
+ int kind;
uint64_t count;
uint64_t accesses;
uint64_t fingerprint;
@@ -63,17 +70,51 @@ static GHashTable *insns; /* pc -> Insn */
static Insn *prev; /* the instruction executed last */
static char *out_path;
static gint vcpus; /* the guest's threads, a vCPU each */
+static gboolean aarch64; /* the guest's ISA: aarch64, else x86_64 */
static const uint64_t fnv_offset = 0xcbf29ce484222325ULL;
static const uint64_t fnv_prime = 0x100000001b3ULL;
-static Insn *insn_at(uint64_t pc, uint64_t size, uintptr_t haddr) {
+/* an x86_64 instruction's opcode: past its legacy and REX prefixes */
+static size_t x86_opcode(const uint8_t *b, size_t n) {
+ size_t k = 0;
+ while (k < n && (b[k] == 0x66 || b[k] == 0x67 || b[k] == 0xf0
+ || b[k] == 0xf2 || b[k] == 0xf3 || b[k] == 0x2e
+ || b[k] == 0x36 || b[k] == 0x3e || b[k] == 0x26
+ || b[k] == 0x64 || b[k] == 0x65))
+ k++;
+ if (k < n && (b[k] & 0xf0) == 0x40) k++;
+ return k;
+}
+
+static int kind_of(const uint8_t *b, size_t n) {
+ if (aarch64) {
+ uint32_t w;
+ if (n < 4) return PLAIN;
+ w = (uint32_t)b[0] | (uint32_t)b[1] << 8 | (uint32_t)b[2] << 16
+ | (uint32_t)b[3] << 24;
+ /* RET Xn, RETAA, RETAB */
+ if ((w & 0xfffffc1f) == 0xd65f0000 || w == 0xd65f0bff
+ || w == 0xd65f0fff)
+ return RETURN;
+ return PLAIN;
+ } else {
+ size_t k = x86_opcode(b, n);
+ /* RET, RET imm16 */
+ if (k < n && (b[k] == 0xc3 || b[k] == 0xc2)) return RETURN;
+ return PLAIN;
+ }
+}
+
+static Insn *insn_at(uint64_t pc, uint64_t size, uintptr_t haddr,
+ int kind) {
Insn *i = g_hash_table_lookup(insns, &pc);
if (i == NULL) {
i = g_new0(Insn, 1);
i->pc = pc;
i->size = size;
i->haddr = haddr;
+ i->kind = kind;
i->fingerprint = fnv_offset;
i->order = fnv_offset;
i->succ = g_hash_table_new_full(g_int64_hash, g_int64_equal,
@@ -134,9 +175,12 @@ static void on_translate(qemu_plugin_id_t id, struct qemu_plugin_tb *tb) {
(void)id;
for (size_t k = 0; k < n; k++) {
struct qemu_plugin_insn *qi = qemu_plugin_tb_get_insn(tb, k);
+ uint8_t bytes[16];
+ size_t len = qemu_plugin_insn_data(qi, bytes, sizeof bytes);
Insn *i = insn_at(qemu_plugin_insn_vaddr(qi),
qemu_plugin_insn_size(qi),
- (uintptr_t)qemu_plugin_insn_haddr(qi));
+ (uintptr_t)qemu_plugin_insn_haddr(qi),
+ kind_of(bytes, len));
qemu_plugin_register_vcpu_insn_exec_cb(qi, on_exec,
QEMU_PLUGIN_CB_NO_REGS, i);
qemu_plugin_register_vcpu_mem_cb(qi, on_mem, QEMU_PLUGIN_CB_NO_REGS,
@@ -276,6 +320,7 @@ static void at_exit(qemu_plugin_id_t id, void *p) {
fprintf(out, "I %" PRIx64 " %" PRIx64 " %" PRIx64 " %016" PRIx64
" %016" PRIx64 " - 0\n", i->pc, i->count, i->accesses,
i->fingerprint, i->order);
+ if (i->kind == RETURN) fprintf(out, "R %" PRIx64 "\n", i->pc);
GHashTableIter jt;
gpointer tk, tn;
g_hash_table_iter_init(&jt, i->succ);
@@ -289,7 +334,7 @@ static void at_exit(qemu_plugin_id_t id, void *p) {
QEMU_PLUGIN_EXPORT int qemu_plugin_install(qemu_plugin_id_t id,
const qemu_info_t *info,
int argc, char **argv) {
- (void)info;
+ aarch64 = strcmp(info->target_name, "aarch64") == 0;
for (int k = 0; k < argc; k++)
if (strncmp(argv[k], "out=", 4) == 0)
out_path = g_strdup(argv[k] + 4);
diff --git a/test/Main.hs b/test/Main.hs
@@ -245,6 +245,20 @@ diffTests = testGroup "diff"
-- in the same order, nothing
dvOrigins (diffDumps [ a, a ]) @?= []
+ , testCase "a return goes where its call sent it: downstream" $ do
+ -- 0x50 returns four times in each run, to 0x30 twice in A and
+ -- three times in B, as the branch at 0x10 sent it
+ a <- either assertFailure pure (readDump (dumpA <> T.unlines
+ [ "I 50 4 0 aaaa 0 /lib.so 50", "R 50", "E 50 30 2"
+ , "E 50 60 2" ]))
+ b <- either assertFailure pure (readDump (dumpB <> T.unlines
+ [ "I 50 4 0 aaaa 0 /lib.so 50", "R 50", "E 50 30 3"
+ , "E 50 60 1" ]))
+ let dv = diffDumps [ a, b ]
+ fmap (\(o, i) -> (o, inPc i)) (dvOrigins dv)
+ @?= [ (ControlOrigin, 0x10), (AddressOrigin, 0x20) ]
+ fmap inPc (dvDownstream dv) @?= [ 0x30, 0x50 ]
+
, testCase "identical runs have no origins" $ do
a <- either assertFailure pure (readDump dumpA)
let dv = diffDumps [ a, a ]
