commit cc5c97fb59c911df9f6727b21cb6e29df071f70a
parent e6ba0a8ba439af99443ca053df69b96a4ae16e23
Author: Jared Tobin <jared@jtobin.io>
Date: Wed, 21 Oct 2026 09:23:56 +0400
diff: a division on other operands is an operand origin
An integer division takes a time that depends on its operands on
most processors, so a division of or by a secret leaks it, as
KyberSlash showed of Kyber's reference code. Neither instrument saw
one: the plugin recorded where instructions branched and what they
addressed, not what they computed on, and memcheck lets an undefined
operand flow into the quotient without a word. synthesis judges a
traced function by its trace, and substratum proves no division
secret, so such a leak was left to censor alone.
The plugin now decodes x86_64's DIV and IDIV and aarch64's UDIV and
SDIV at translation, and for each keeps an order-sensitive
fingerprint of the values it divided: before it runs, the dividend
(AX, or DX:AX to RDX:RAX, by width) and a register divisor, read
through QEMU's register interface, masked to the width; a divisor in
memory as it is loaded, through the value QEMU reports for the
access. A D line gives each division's fingerprint. diff reports a
division run equally often in every declared run, on other operands
in one, as an `operand` origin, grouped by the runs alike there; a
control dividing other operands sets it apart as unsteady, and a
designed run speaks to it no more than to an address.
The probe harness divides a secret by a public modulus, the divisor
in a register, and a public value by a secret, the divisor read from
memory; the check finds both, on x86_64 and on aarch64, and fails
without the memory path.
Diffstat:
7 files changed, 291 insertions(+), 76 deletions(-)
diff --git a/CHANGELOG b/CHANGELOG
@@ -15,7 +15,8 @@
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, a return never one, and what ran downstream listed
+ origin too, a return never one, an integer division on other
+ operands an `operand` origin, 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
diff --git a/README.md b/README.md
@@ -57,9 +57,10 @@ control 0x4878d4d next<&[u64]> bits.rs:32 x982
### Differential traces: `vestigia record` and `vestigia diff`
`record` runs the harness under QEMU with a plugin that summarises,
-per instruction, how often it ran, where it branched, and which
-addresses it touched. Record several runs differing only in the
-secret, and `diff` reports where they diverge:
+per instruction, how often it ran, where it branched, which addresses
+it touched, and, for an integer division, which operands it divided.
+Record several runs differing only in the secret, and `diff` reports
+where they diverge:
```
$ for s in 1 2 3; do
@@ -75,8 +76,10 @@ 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
+proportion or in order (`control`), an instruction whose addresses
+differ (`address`), or a division, whose time depends on its
+operands, on other operands (`operand`). Each names the runs that
+behaved alike there. Instructions that
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.
@@ -85,7 +88,7 @@ them; and every instruction some run executed is listed as coverage.
between the two is *unsteady* and kept out of the origins.
* `--designed DUMP` is a run whose secret was chosen to reach a
particular path. It counts toward control origins and coverage,
- never toward address origins.
+ never toward address or operand origins.
* `--object TEXT` keeps the report to matching objects.
`record` disables address-space randomisation and seeds the guest's
diff --git a/etc/probe/harness.c b/etc/probe/harness.c
@@ -7,8 +7,8 @@
*
* Its secret, the first argument in hex (of one width for every
* 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.
+ * table index, which of two calls a helper returns to, a dividend,
+ * and a divisor; a constant-time select reaches none of them.
*/
#include <stdio.h>
#include <stdlib.h>
@@ -16,6 +16,7 @@
#include "vestigia.h"
static unsigned char table[256];
+static volatile unsigned modulus = 3329;
__attribute__((noinline)) unsigned branchy(unsigned s) {
unsigned r = 0;
@@ -42,6 +43,34 @@ __attribute__((noinline)) unsigned calls(unsigned s) {
return r;
}
+/* a secret divided by a public modulus, the divisor in a register */
+__attribute__((noinline)) unsigned divide(unsigned s) {
+#if defined(__x86_64__)
+ unsigned q, r;
+ __asm__ volatile("divl %4"
+ : "=a"(q), "=d"(r)
+ : "a"(s * 2654435761u), "d"(0u), "r"(modulus));
+ return q ^ r;
+#else
+ return (s * 2654435761u) / modulus;
+#endif
+}
+
+/* a public value divided by a secret, which x86_64 reads from memory
+ as the division's operand */
+__attribute__((noinline)) unsigned divide_memory(unsigned s) {
+ unsigned d = (s & 0xffu) | 1u;
+#if defined(__x86_64__)
+ unsigned q, r;
+ __asm__ volatile("divl %4"
+ : "=a"(q), "=d"(r)
+ : "a"(1000003u), "d"(0u), "m"(d));
+ return q ^ r;
+#else
+ return 1000003u / d;
+#endif
+}
+
__attribute__((noinline)) unsigned ct(unsigned s, unsigned p) {
unsigned m = 0u - (p & 1u);
return (s & m) | (~s & ~m);
@@ -49,14 +78,17 @@ __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[4];
+ unsigned out[6];
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] = calls(s);
- out[3] = ct(s, 1);
+ out[3] = divide(s);
+ out[4] = divide_memory(s);
+ out[5] = ct(s, 1);
vestigia_public(out, sizeof out);
- printf("%u %u %u %u\n", out[0], out[1], out[2], out[3]);
+ printf("%u %u %u %u %u %u\n", out[0], out[1], out[2], out[3], out[4],
+ out[5]);
return 0;
}
diff --git a/lib/Vestigia/Diff.hs b/lib/Vestigia/Diff.hs
@@ -10,7 +10,8 @@
-- Where runs that differ only in a secret differ. Each run is a
-- leakage trace summarised per instruction (the QEMU plugin's
-- dump): how often each instruction ran, how often it transferred
--- to each target, and a fingerprint of the addresses it touched.
+-- to each target, a fingerprint of the addresses it touched, and,
+-- for an integer division, a fingerprint of its operands.
--
-- A branch whose outcome did not depend on the secret takes each
-- of its transfers in the same proportion however often it runs; a
@@ -21,7 +22,9 @@
-- taking each transfer as often, in another order: the plugin keeps
-- an order-sensitive fingerprint of what followed each instruction.
-- An instruction run equally often in every run whose addresses
--- differ computed one from the secret: an `address` origin. Every
+-- differ computed one from the secret: an `address` origin. A
+-- division, whose time depends on its operands, run equally often
+-- on other operands is an `operand` origin. Every
-- other instruction run a different number of times sits where
-- control had already diverged: it is downstream. So is a return
-- whose transfers differ, however often it ran: it goes where the
@@ -45,8 +48,9 @@
-- only in the secret, so an instruction's addresses differing in one
-- of them says nothing about the secret. A designed run counts toward
-- the control origins (a branch whose outcomes shift under it chose
--- by the secret) and what was executed, never toward the address
--- origins, which only runs alike in all but the secret can show.
+-- by the secret) and what was executed, never toward the address or
+-- operand origins, which only runs alike in all but the secret can
+-- show.
--
-- What every run executed, per object, is reported beside: the
-- instructions the chosen secrets exercised, and so, against what
@@ -55,7 +59,8 @@
-- Each origin names how the runs behaved there: the runs alike at
-- it, grouped (taking each transfer in the same proportion, at a
-- control origin; touching the same addresses, at an address
--- origin), and the runs that never reached it. Whether two runs
+-- origin; dividing the same operands, at an operand origin), and the
+-- runs that never reached it. Whether two runs
-- that differed there both had their secrets accepted is the
-- reader's to say, from what each run returned.
@@ -116,12 +121,14 @@ data Run = Run {
} deriving (Eq, Show)
-- | One run: its instructions by address, its transfers by source,
--- each a count per target, the instructions that return, and how
--- it was made, where its dump says.
+-- each a count per target, the instructions that return, the
+-- divisions' operands, fingerprinted, 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)
+ , dpOperands :: !(M.Map Integer T.Text)
, dpRun :: !(Maybe Run)
} deriving (Eq, Show)
@@ -134,12 +141,13 @@ 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 S.empty [] Nothing Nothing
+readDump t =
+ go (T.lines t) M.empty M.empty S.empty M.empty [] Nothing Nothing
where
- go ls is es rs as env st = case ls of
+ go ls is es rs ds as env st = case ls of
[]
| any ((> 0) . inCount) (M.elems is) ->
- Dump is es rs <$> record (reverse as) env st
+ Dump is es rs ds <$> record (reverse as) env st
| otherwise ->
Left "no instruction ran: the run was not recorded"
(l : rest) -> case T.words l of
@@ -148,30 +156,33 @@ readDump t = go (T.lines t) M.empty M.empty S.empty [] Nothing Nothing
<*> pure ord
<*> pure (if obj == "-" then Nothing else Just obj)
<*> unhex off
- go rest (M.insert (inPc i) i is) es rs as env st
+ go rest (M.insert (inPc i) i is) es rs ds 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)
- rs as env st
+ rs ds as env st
[ "R", pc ] -> do
r <- unhex pc
- go rest is es (S.insert r rs) as env st
+ go rest is es (S.insert r rs) ds as env st
+ [ "D", pc, fp ] -> do
+ k <- unhex pc
+ go rest is es rs (M.insert k fp ds) 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 rs (BS.empty : as) env st
+ [ "A" ] -> go rest is es rs ds (BS.empty : as) env st
[ "A", h ] -> do
b <- unhexBytes h
- go rest is es rs (b : as) env st
+ go rest is es rs ds (b : as) env st
[ "N", n, b ] -> do
v <- (,) <$> unhex n <*> unhex b
- go rest is es rs as (Just v) st
+ go rest is es rs ds as (Just v) st
[ "X", x ] -> case readMaybe (T.unpack x) of
- Just v -> go rest is es rs as env (Just v)
+ Just v -> go rest is es rs ds as env (Just v)
Nothing -> Left ("not an exit status: " <> T.unpack x)
- [] -> go rest is es rs as env st
+ [] -> go rest is es rs ds as env st
_ -> Left ("an unreadable dump line: " <> T.unpack l)
record as env st = case (as, env, st) of
([], Nothing, Nothing) -> pure Nothing
@@ -242,6 +253,7 @@ layoutApart a b =
data Origin =
ControlOrigin
| AddressOrigin
+ | OperandOrigin
deriving (Eq, Ord, Show)
-- | Where the runs differ: the origins, each an instruction run
@@ -251,7 +263,8 @@ data Divergence = Divergence {
dvOrigins :: ![(Origin, Insn)]
-- | at each origin, the runs alike there, grouped, and the runs
-- that never reached it, as indices into the declared runs
- -- then the designed (an address origin's, the declared alone)
+ -- then the designed (an address or operand origin's, the
+ -- declared alone)
, dvBehaviour :: !(M.Map (Origin, Integer) ([[Int]], [Int]))
, dvDownstream :: ![Insn]
, dvUnsteady :: ![Insn]
@@ -274,8 +287,9 @@ diffControlled :: [Dump] -> [Dump] -> Divergence
diffControlled cs ds = diffDesigned cs ds []
-- | Compare runs, given controls and runs designed to reach particular
--- paths. The address origins are the declared runs' alone; the
--- control origins and what was executed are every run's.
+-- paths. The address and operand origins are the declared runs'
+-- alone; the control origins and what was executed are every
+-- run's.
diffDesigned :: [Dump] -> [Dump] -> [Dump] -> Divergence
diffDesigned cs ds xs = Divergence {
dvOrigins = L.sortOn (inPc . snd) origins
@@ -309,10 +323,11 @@ diffDesigned cs ds xs = Divergence {
ib = M.lookup pc (dpInsns b)
ta = M.lookup pc (dpTransfers a)
tb = M.lookup pc (dpTransfers b)
- , fmap sig ia /= fmap sig ib || ta /= tb ]
+ , fmap sig ia /= fmap sig ib || ta /= tb
+ || M.lookup pc (dpOperands a) /= M.lookup pc (dpOperands b) ]
sig i = (inCount i, inFingerprint i, inOrder i)
- origins = [ o | o@(_, i) <- controls <> addresses
+ origins = [ o | o@(_, i) <- controls <> addresses <> operands
, not (inPc i `S.member` unsteady) ]
-- every run, the declared first
@@ -320,7 +335,7 @@ diffDesigned cs ds xs = Divergence {
-- how the runs behaved at an origin: those that ran it, grouped
-- by what they did there, and those that never ran it. Only the
- -- declared runs speak to an address.
+ -- declared runs speak to an address or an operand.
behaviourAt o pc = case o of
ControlOrigin ->
( classes outcomesAlike
@@ -331,6 +346,10 @@ diffDesigned cs ds xs = Divergence {
AddressOrigin ->
( classes (==) [ (k, inFingerprint i) | (k, _, i) <- ranIn ds ]
, absentIn ds )
+ OperandOrigin ->
+ ( classes (==)
+ [ (k, M.lookup pc (dpOperands d)) | (k, d, _) <- ranIn ds ]
+ , absentIn ds )
where
ranIn rs = [ (k, d, i) | (k, d) <- zip [ 0 .. ] rs
, Just i <- [ M.lookup pc (dpInsns d) ]
@@ -385,12 +404,13 @@ diffDesigned cs ds xs = Divergence {
returns = S.unions (fmap dpReturns runs)
divergentPcs = S.filter divergent transferSources
controlPcs = divergentPcs `S.difference` returns
- addressPcs = S.fromList [ inPc i | (_, i) <- addresses ]
+ -- the address and operand origins
+ dataPcs = S.fromList [ inPc i | (_, i) <- addresses <> operands ]
downstream =
(((pcs `S.difference` steady)
`S.union` (divergentPcs `S.intersection` returns))
`S.difference` controlPcs)
- `S.difference` addressPcs
+ `S.difference` dataPcs
controls =
[ (ControlOrigin, i)
@@ -406,6 +426,16 @@ diffDesigned cs ds xs = Divergence {
, Just i <- [ firstInsn pc ]
, inAccesses i > 0 ]
+ -- a division run equally often in every declared run, on other
+ -- operands in one
+ operands =
+ [ (OperandOrigin, i)
+ | pc <- S.toAscList steadyDeclared
+ , let fps = [ M.lookup pc (dpOperands d) | d <- ds ]
+ , any (/= Nothing) fps
+ , not (alike fps)
+ , Just i <- [ firstInsn pc ] ]
+
-- | Only the origins, what was executed, and what ran downstream, in
-- objects whose path contains one of the given texts.
restrictTo :: [T.Text] -> Divergence -> Divergence
@@ -426,6 +456,7 @@ originText :: Origin -> T.Text
originText o = case o of
ControlOrigin -> "control"
AddressOrigin -> "address"
+ OperandOrigin -> "operand"
-- | The report: @vestigia/diff-v3@. Runs are given the declared,
-- then the designed, then the controls, and an origin names the
@@ -450,6 +481,7 @@ divergenceJson version runs places dv = Object
, ("summary", Object
[ ("control", count ControlOrigin)
, ("address", count AddressOrigin)
+ , ("operand", count OperandOrigin)
, ("downstream", Number (toInteger (length (dvDownstream dv))))
, ("unsteady", Number (toInteger (length (dvUnsteady dv))))
])
diff --git a/nix/probe.nix b/nix/probe.nix
@@ -54,7 +54,8 @@ let
trace = [ [ "address" "lookup" ] [ "control" "branchy" ]
[ "control" "calls" ] ];
diff = [ [ "address" "lookup" ] [ "control" "branchy" ]
- [ "control" "calls" ] ];
+ [ "control" "calls" ] [ "operand" "divide" ]
+ [ "operand" "divide_memory" ] ];
};
in
pkgs.runCommand "vestigia-probe-check" {
diff --git a/plugin/vestigia-qemu.c b/plugin/vestigia-qemu.c
@@ -16,24 +16,30 @@
* 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. It marks the
- * instructions that return (x86_64's and aarch64's), which go where
- * the call before them sent them.
+ * control flow are seen as well as those of data flow.
+ *
+ * It reads each instruction's bytes, x86_64's or aarch64's, for two
+ * kinds. A return goes where the call before it sent it, and is
+ * marked. An integer division takes a time that depends on its
+ * operands, so it gets an order-sensitive fingerprint of their
+ * values: the dividend and a register divisor read before it runs,
+ * and a divisor in memory as it is loaded. A division run as often
+ * but on other operands computed them from the secret.
*
* 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.
+ * D <pc> <operands>
*
* in hex, where <object> is the file the instruction's bytes were
* mapped from ("-" if none, or if the file's program headers cannot
* be read) and <address> its address in that file: where the file's
* program headers place it, as its disassembly and line tables name
* it. In a shared library that is often the instruction's offset in
- * the file; in an executable linked at a fixed address it is not.
+ * the file; in an executable linked at a fixed address it is not. A
+ * guest that started a second thread gets the line `T 2` alone.
*
* The state below is unlocked, so one guest thread is recorded: a
* guest that starts a second one is stopped there, its dump saying
@@ -52,17 +58,30 @@
QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
/* what an instruction is to a comparison, read from its bytes */
-enum { PLAIN, RETURN };
+enum { PLAIN, RETURN, DIVISION };
+
+/* registers by number: x86_64's in ModRM order, aarch64's X0 to X30;
+ aarch64's 31 is the zero register where a division names it */
+enum { RAX = 0, RDX = 2, ZR = 31, GPRS = 32 };
+
+typedef struct Decoded {
+ int kind;
+ /* a division's: its width in bits; on aarch64 its two registers,
+ on x86_64 its divisor's (-1 in memory), that register's second
+ byte where `high`, the dividend being RDX:RAX or AX */
+ int width, a, b, high;
+} Decoded;
typedef struct Insn {
uint64_t pc;
uint64_t size;
uintptr_t haddr;
- int kind;
+ Decoded d;
uint64_t count;
uint64_t accesses;
uint64_t fingerprint;
uint64_t order; /* the successors, in the order they followed */
+ uint64_t operands; /* a division's operands, in order */
GHashTable *succ; /* target pc -> count, for transfers */
} Insn;
@@ -71,52 +90,77 @@ 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 struct qemu_plugin_register *gpr[GPRS];
+static GByteArray *regbuf;
static const uint64_t fnv_offset = 0xcbf29ce484222325ULL;
static const uint64_t fnv_prime = 0x100000001b3ULL;
-/* an x86_64 instruction's opcode: past its legacy and REX prefixes */
-static size_t x86_opcode(const uint8_t *b, size_t n) {
+static Decoded decode_aarch64(const uint8_t *b, size_t n) {
+ Decoded d = { PLAIN, 0, 0, 0, 0 };
+ uint32_t w;
+ if (n < 4) return d;
+ 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)
+ d.kind = RETURN;
+ /* UDIV, SDIV */
+ else if ((w & 0x7fe0f800) == 0x1ac00800) {
+ d.kind = DIVISION;
+ d.width = (w >> 31) ? 64 : 32;
+ d.a = (int)((w >> 5) & 31);
+ d.b = (int)((w >> 16) & 31);
+ }
+ return d;
+}
+
+static Decoded decode_x86_64(const uint8_t *b, size_t n) {
+ Decoded d = { PLAIN, 0, 0, 0, 0 };
size_t k = 0;
+ int opsize = 0, rex = 0;
+ /* past the legacy prefixes, then a REX */
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))
+ || b[k] == 0x64 || b[k] == 0x65)) {
+ if (b[k] == 0x66) opsize = 1;
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;
}
+ if (k < n && (b[k] & 0xf0) == 0x40) rex = b[k++];
+ if (k >= n) return d;
+ /* RET, RET imm16 */
+ if (b[k] == 0xc3 || b[k] == 0xc2) d.kind = RETURN;
+ /* DIV, IDIV: F6 or F7 with ModRM's reg 6 or 7 */
+ else if ((b[k] == 0xf6 || b[k] == 0xf7) && k + 1 < n
+ && ((b[k + 1] >> 3) & 6) == 6) {
+ int modrm = b[k + 1], rm = modrm & 7;
+ d.kind = DIVISION;
+ d.width = b[k] == 0xf6 ? 8 : (rex & 8) ? 64 : opsize ? 16 : 32;
+ if ((modrm >> 6) != 3) d.a = -1;
+ /* without REX, a byte register 4 to 7 is AH, CH, DH, or BH */
+ else if (d.width == 8 && rex == 0 && rm >= 4) {
+ d.a = rm - 4;
+ d.high = 1;
+ } else
+ d.a = rm | ((rex & 1) << 3);
+ }
+ return d;
}
static Insn *insn_at(uint64_t pc, uint64_t size, uintptr_t haddr,
- int kind) {
+ Decoded d) {
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->d = d;
i->fingerprint = fnv_offset;
i->order = fnv_offset;
+ i->operands = fnv_offset;
i->succ = g_hash_table_new_full(g_int64_hash, g_int64_equal,
g_free, g_free);
g_hash_table_insert(insns, &i->pc, i);
@@ -146,19 +190,95 @@ static void on_exec(unsigned int vcpu, void *udata) {
i->count++;
}
+static void mix(Insn *i, uint64_t v) {
+ i->operands = (i->operands ^ v) * fnv_prime;
+}
+
+static uint64_t read_gpr(int r) {
+ uint64_t v = 0;
+ int n;
+ if (aarch64 && r == ZR) return 0;
+ g_byte_array_set_size(regbuf, 0);
+ n = qemu_plugin_read_register(gpr[r], regbuf);
+ /* in the guest's byte order, little-endian as the host's */
+ if (n > 0) memcpy(&v, regbuf->data, MIN((size_t)n, sizeof v));
+ return v;
+}
+
+static void on_divide(unsigned int vcpu, void *udata) {
+ Insn *i = udata;
+ uint64_t mask = i->d.width == 64 ? ~0ULL : (1ULL << i->d.width) - 1;
+ (void)vcpu;
+ if (aarch64) {
+ mix(i, read_gpr(i->d.a) & mask);
+ mix(i, read_gpr(i->d.b) & mask);
+ return;
+ }
+ if (i->d.width == 8)
+ mix(i, read_gpr(RAX) & 0xffff);
+ else {
+ mix(i, read_gpr(RAX) & mask);
+ mix(i, read_gpr(RDX) & mask);
+ }
+ /* a divisor in memory is mixed in as it is loaded */
+ if (i->d.a >= 0)
+ mix(i, (read_gpr(i->d.a) >> (i->d.high ? 8 : 0)) & mask);
+}
+
static void on_mem(unsigned int vcpu, qemu_plugin_meminfo_t info,
uint64_t vaddr, void *udata) {
Insn *i = udata;
(void)vcpu;
- (void)info;
i->fingerprint = (i->fingerprint ^ vaddr) * fnv_prime;
i->accesses++;
+ if (i->d.kind == DIVISION) {
+ qemu_plugin_mem_value v = qemu_plugin_mem_get_value(info);
+ switch (v.type) {
+ case QEMU_PLUGIN_MEM_VALUE_U8: mix(i, v.data.u8); break;
+ case QEMU_PLUGIN_MEM_VALUE_U16: mix(i, v.data.u16); break;
+ case QEMU_PLUGIN_MEM_VALUE_U32: mix(i, v.data.u32); break;
+ case QEMU_PLUGIN_MEM_VALUE_U64: mix(i, v.data.u64); break;
+ case QEMU_PLUGIN_MEM_VALUE_U128:
+ mix(i, v.data.u128.low);
+ mix(i, v.data.u128.high);
+ break;
+ }
+ }
+}
+
+/* the general registers a division reads, by the names QEMU's
+ debugger stub gives them */
+static void find_registers(void) {
+ static const char *x86_64[16] = {
+ "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi",
+ "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15" };
+ GArray *rs = qemu_plugin_get_registers();
+ int wanted = aarch64 ? 31 : 16;
+ for (guint k = 0; k < rs->len; k++) {
+ qemu_plugin_reg_descriptor *r =
+ &g_array_index(rs, qemu_plugin_reg_descriptor, k);
+ for (int j = 0; j < wanted; j++) {
+ char name[8];
+ if (aarch64) g_snprintf(name, sizeof name, "x%d", j);
+ if (strcmp(r->name, aarch64 ? name : x86_64[j]) == 0)
+ gpr[j] = r->handle;
+ }
+ }
+ g_array_free(rs, TRUE);
+ for (int j = 0; j < wanted; j++)
+ if (gpr[j] == NULL) {
+ fprintf(stderr, "vestigia-qemu: QEMU names no register %d, by "
+ "which a division's operands are read\n", j);
+ _exit(EXIT_FAILURE);
+ }
}
static void on_vcpu_init(qemu_plugin_id_t id, unsigned int vcpu) {
(void)id;
(void)vcpu;
- if (g_atomic_int_add(&vcpus, 1) > 0) {
+ if (g_atomic_int_add(&vcpus, 1) == 0)
+ find_registers();
+ else {
FILE *out = fopen(out_path, "w");
if (out != NULL) {
fprintf(out, "T 2\n");
@@ -180,9 +300,13 @@ static void on_translate(qemu_plugin_id_t id, struct qemu_plugin_tb *tb) {
Insn *i = insn_at(qemu_plugin_insn_vaddr(qi),
qemu_plugin_insn_size(qi),
(uintptr_t)qemu_plugin_insn_haddr(qi),
- kind_of(bytes, len));
+ aarch64 ? decode_aarch64(bytes, len)
+ : decode_x86_64(bytes, len));
qemu_plugin_register_vcpu_insn_exec_cb(qi, on_exec,
QEMU_PLUGIN_CB_NO_REGS, i);
+ if (i->d.kind == DIVISION)
+ qemu_plugin_register_vcpu_insn_exec_cb(qi, on_divide,
+ QEMU_PLUGIN_CB_R_REGS, i);
qemu_plugin_register_vcpu_mem_cb(qi, on_mem, QEMU_PLUGIN_CB_NO_REGS,
QEMU_PLUGIN_MEM_RW, i);
}
@@ -320,7 +444,9 @@ 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);
+ if (i->d.kind == RETURN) fprintf(out, "R %" PRIx64 "\n", i->pc);
+ if (i->d.kind == DIVISION)
+ fprintf(out, "D %" PRIx64 " %016" PRIx64 "\n", i->pc, i->operands);
GHashTableIter jt;
gpointer tk, tn;
g_hash_table_iter_init(&jt, i->succ);
@@ -343,6 +469,7 @@ QEMU_PLUGIN_EXPORT int qemu_plugin_install(qemu_plugin_id_t id,
return -1;
}
insns = g_hash_table_new(g_int64_hash, g_int64_equal);
+ regbuf = g_byte_array_new();
qemu_plugin_register_vcpu_init_cb(id, on_vcpu_init);
qemu_plugin_register_vcpu_tb_trans_cb(id, on_translate);
qemu_plugin_register_atexit_cb(id, at_exit, NULL);
diff --git a/test/Main.hs b/test/Main.hs
@@ -259,6 +259,25 @@ diffTests = testGroup "diff"
@?= [ (ControlOrigin, 0x10), (AddressOrigin, 0x20) ]
fmap inPc (dvDownstream dv) @?= [ 0x30, 0x50 ]
+ , testCase "a division on other operands is an operand origin" $ do
+ -- 0x40 divides once in every run, on other operands in B; in a
+ -- designed run, on others again
+ a <- either assertFailure pure (readDump (dumpA <> "D 40 1111\n"))
+ b <- either assertFailure pure (readDump (dumpB <> "D 40 2222\n"))
+ x <- either assertFailure pure (readDump (dumpA <> "D 40 3333\n"))
+ let dv = diffDumps [ a, b ]
+ fmap (\(o, i) -> (o, inPc i)) (dvOrigins dv)
+ @?= [ (ControlOrigin, 0x10), (AddressOrigin, 0x20)
+ , (OperandOrigin, 0x40) ]
+ M.lookup (OperandOrigin, 0x40) (dvBehaviour (diffDumps [ a, b, a ]))
+ @?= Just ([ [ 0, 2 ], [ 1 ] ], [])
+ notElem 0x40 (fmap inPc (dvDownstream dv)) @? "downstream"
+ -- a designed run's operands say nothing of the secret
+ fmap (\(o, i) -> (o, inPc i)) (dvOrigins (diffDesigned [] [ a, a ]
+ [ x ])) @?= []
+ -- a control dividing other operands sets it apart as unsteady
+ fmap inPc (dvUnsteady (diffControlled [ x ] [ a, b ])) @?= [ 0x40 ]
+
, testCase "identical runs have no origins" $ do
a <- either assertFailure pure (readDump dumpA)
let dv = diffDumps [ a, a ]
