commit 3b28eb354393ee5d36e747b3489f70591b438764
parent d46bfe999c7d30bc3eb120bbab1f68471653a533
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 17 Oct 2026 20:11:35 +0400
vestigia: differential leakage traces under QEMU, and the Penumbra spike
Diffstat:
11 files changed, 867 insertions(+), 19 deletions(-)
diff --git a/app/Main.hs b/app/Main.hs
@@ -27,14 +27,23 @@ import System.IO (hClose, hPutStrLn, openTempFile, stderr)
import System.Process (proc, waitForProcess, withCreateProcess)
import Paths_vestigia (version)
+import Vestigia.Diff
+ (diffDumps, divergenceJson, divergenceSummary, dvOrigins, inObject,
+ inOffset, readDump, restrictTo)
import Vestigia.Json (encode)
import Vestigia.Memcheck (readMemcheck)
+import Vestigia.Symbol (symbolize)
import Vestigia.Trace (trace, traceJson, traceSummary)
data Opts = Opts {
oValgrind :: !(Maybe FilePath)
, oXml :: !(Maybe FilePath)
, oOut :: !(Maybe FilePath)
+ , oQemu :: !(Maybe FilePath)
+ , oPlugin :: !(Maybe FilePath)
+ , oDump :: !(Maybe FilePath)
+ , oAddr2line :: !(Maybe FilePath)
+ , oObjects :: ![T.Text]
}
main :: IO ()
@@ -49,6 +58,14 @@ main = do
Right (o, [ xml ]) -> readXml o xml
Right _ -> usage "read: one XML file expected"
Left e -> usage e
+ ("record" : rest) -> case options rest of
+ Right (o, prog : progArgs) -> record o prog progArgs
+ Right (_, []) -> usage "record: no program given"
+ Left e -> usage e
+ ("diff" : rest) -> case options rest of
+ Right (o, dumps@(_ : _ : _)) -> diff o dumps
+ Right _ -> usage "diff: two or more dumps expected"
+ Left e -> usage e
[ "--version" ] -> putStrLn (showVersion version)
_ -> usage "expected a command"
@@ -60,23 +77,42 @@ usage e = do
, " vestigia run [--valgrind PATH] [--xml FILE] [--out FILE] \
\-- PROGRAM [ARG...]"
, " vestigia read [--out FILE] FILE.xml"
+ , " vestigia record [--qemu PATH] [--plugin PATH] --dump FILE \
+ \-- PROGRAM [ARG...]"
+ , " vestigia diff [--out FILE] [--addr2line PATH] \
+ \[--object TEXT]... DUMP DUMP..."
, ""
, "run executes PROGRAM under memcheck, which reports every"
, "branch and address that depended on bytes the program marked"
, "secret (vestigia.h), and writes the report (vestigia/trace-v1)."
, "valgrind is --valgrind, else $VESTIGIA_VALGRIND, else on PATH."
+ , ""
+ , "record executes PROGRAM under QEMU with vestigia's plugin and"
+ , "dumps its leakage trace per instruction; diff compares dumps"
+ , "of runs that differ only in a secret and reports where they"
+ , "diverge (vestigia/diff-v1), naming sources with addr2line."
+ , "--object keeps origins in objects whose path contains TEXT."
+ , "qemu, the plugin, and addr2line default to $VESTIGIA_QEMU,"
+ , "$VESTIGIA_PLUGIN, and $VESTIGIA_ADDR2LINE."
]
exitWith (ExitFailure 2)
-- options before the program; "--" ends them
options :: [String] -> Either String (Opts, [String])
-options = go (Opts Nothing Nothing Nothing)
+options = go (Opts Nothing Nothing Nothing Nothing Nothing Nothing
+ Nothing [])
where
go o xs = case xs of
("--" : rest) -> Right (o, rest)
("--valgrind" : p : rest) -> go o { oValgrind = Just p } rest
("--xml" : p : rest) -> go o { oXml = Just p } rest
("--out" : p : rest) -> go o { oOut = Just p } rest
+ ("--qemu" : p : rest) -> go o { oQemu = Just p } rest
+ ("--plugin" : p : rest) -> go o { oPlugin = Just p } rest
+ ("--dump" : p : rest) -> go o { oDump = Just p } rest
+ ("--addr2line" : p : rest) -> go o { oAddr2line = Just p } rest
+ ("--object" : t : rest) ->
+ go o { oObjects = oObjects o <> [ T.pack t ] } rest
(x : _) | take 2 x == "--" -> Left ("unknown option: " <> x)
_ -> Right (o, xs)
@@ -141,3 +177,47 @@ report o exit xml = do
(traceJson (T.pack (showVersion version)) exit tr)
maybe (TIO.putStr doc) (\p -> TIO.writeFile p doc) (oOut o)
TIO.hPutStr stderr (traceSummary tr)
+
+-- a tool named by its option, else its environment variable, else
+-- the given default
+tool :: Maybe FilePath -> String -> String -> IO FilePath
+tool opt var dflt = do
+ env <- lookupEnv var
+ pure (maybe (maybe dflt id env) id opt)
+
+record :: Opts -> FilePath -> [String] -> IO ()
+record o prog progArgs = do
+ dump <- maybe (usage "record: --dump FILE is needed") pure (oDump o)
+ qemu <- tool (oQemu o) "VESTIGIA_QEMU" "qemu-x86_64"
+ plugin <- tool (oPlugin o) "VESTIGIA_PLUGIN" "libvestigia-qemu.so"
+ r <- try (withCreateProcess
+ (proc qemu ([ "-plugin", plugin <> ",out=" <> dump, prog ]
+ <> progArgs))
+ (\_ _ _ ph -> waitForProcess ph))
+ case r of
+ Left e -> do
+ hPutStrLn stderr ("vestigia: cannot run " <> qemu <> ": "
+ <> show (e :: IOException))
+ exitWith (ExitFailure 2)
+ Right c -> exitWith c
+
+diff :: Opts -> [FilePath] -> IO ()
+diff o paths = do
+ addr2line <- tool (oAddr2line o) "VESTIGIA_ADDR2LINE" "addr2line"
+ dumps <- traverse readOne paths
+ let dv = restrictTo (oObjects o) (diffDumps dumps)
+ places <- symbolize addr2line
+ [ (obj, inOffset i) | (_, i) <- dvOrigins dv
+ , Just obj <- [ inObject i ] ]
+ let doc = encode
+ (divergenceJson (T.pack (showVersion version)) places dv)
+ maybe (TIO.putStr doc) (\p -> TIO.writeFile p doc) (oOut o)
+ TIO.hPutStr stderr (divergenceSummary places dv)
+ where
+ readOne p = do
+ bytes <- BS.readFile p
+ case readDump (TE.decodeUtf8With TEE.lenientDecode bytes) of
+ Left e -> do
+ hPutStrLn stderr ("vestigia: " <> p <> ": " <> e)
+ exitWith (ExitFailure 2)
+ Right d -> pure d
diff --git a/etc/probe/diffprobe.c b/etc/probe/diffprobe.c
@@ -0,0 +1,32 @@
+/* A secret chosen by the first argument (same width for every
+ * secret, so the stack lays out the same) reaching a branch and a
+ * table index, and a constant-time select that touches neither. */
+#include <stdio.h>
+#include <stdlib.h>
+
+static unsigned char table[256];
+
+__attribute__((noinline)) int branchy(unsigned s) {
+ int r = 0;
+ for (unsigned i = 0; i < (s & 7); i++) r += i;
+ return r;
+}
+
+__attribute__((noinline)) int lookup(unsigned s) {
+ return table[s & 0xff];
+}
+
+__attribute__((noinline)) unsigned ct(unsigned s, unsigned p) {
+ unsigned m = 0u - (p & 1u);
+ return (s & m) | (s ^ m);
+}
+
+int main(int argc, char **argv) {
+ unsigned s = (unsigned)strtoul(argc > 1 ? argv[1] : "00", NULL, 16);
+ for (int i = 0; i < 256; i++) table[i] = (unsigned char)i;
+ int a = branchy(s);
+ int b = lookup(s);
+ unsigned c = ct(s, 1);
+ printf("%d %d %u\n", a, b, c);
+ return 0;
+}
diff --git a/etc/probe/diffprobe.nix b/etc/probe/diffprobe.nix
@@ -0,0 +1,23 @@
+let
+ f = builtins.getFlake "/Users/jtobin/src/ppad/vestigia";
+ pkgs = import f.inputs.nixpkgs { system = "x86_64-linux"; };
+ plugin = pkgs.runCommandCC "vestigia-qemu-plugin" {
+ nativeBuildInputs = [ pkgs.pkg-config ];
+ buildInputs = [ pkgs.glib ];
+ } ''
+ mkdir -p $out/lib
+ cc -O2 -shared -fPIC -Wall -Werror \
+ $(pkg-config --cflags glib-2.0) -I${pkgs.qemu}/include \
+ -o $out/lib/libvestigia-qemu.so ${../../plugin/vestigia-qemu.c}
+ '';
+in pkgs.runCommandCC "vestigia-diffprobe" { } ''
+ mkdir -p $out
+ cc -O2 -g -o probe ${./diffprobe.c}
+ for s in 03 05; do
+ ${pkgs.qemu}/bin/qemu-x86_64 \
+ -plugin ${plugin}/lib/libvestigia-qemu.so,out=$out/dump-$s \
+ ./probe $s > $out/stdout-$s
+ done
+ objdump -d probe > $out/probe.dis
+ cp probe $out/
+''
diff --git a/etc/spike/penumbra/default.nix b/etc/spike/penumbra/default.nix
@@ -39,10 +39,23 @@ let
};
roots = [ "public_key" "key_agreement" "spend_auth_sign" ];
+
+ # three processes of two calls each, differing only in the secrets
+ seeds = [ "0000000000000001" "0000000000000002" "0000000000000003" ];
+ diffOf = build: lib: root: vestigia.lib.${system}.diffOf {
+ name = "penumbra-${build}-${root}";
+ harness = "${harnessFor lib}/bin/harness";
+ runs = map (s: [ root "2" s ]) seeds;
+ objects = [ "libpenumbra_audit" ];
+ };
in
{
inherit audited lines;
+ diffs = pkgs.linkFarm "penumbra-diffs" (
+ map (r: { name = "lines/${r}"; path = diffOf "lines" lines r; })
+ roots);
+
traces = pkgs.linkFarm "penumbra-traces" (
map (r: { name = "audited/${r}"; path = traceOf "audited" audited r; })
roots
diff --git a/etc/spike/penumbra/harness.c b/etc/spike/penumbra/harness.c
@@ -3,8 +3,11 @@
* fresh random secrets, marked secret before the call, with the
* outputs Penumbra reveals marked public after it.
*
- * usage: harness ROOT [RUNS]
+ * usage: harness ROOT [RUNS [SEED]]
* ROOT is public_key, key_agreement, or spend_auth_sign
+ * SEED (16 hex digits) seeds the secrets alone; public inputs come
+ * from a fixed stream, so runs that differ in SEED differ only in
+ * their secrets.
*/
#include <stdint.h>
#include <stdio.h>
@@ -17,29 +20,30 @@ void penumbra_audit_public_key(uint8_t *ws);
void penumbra_audit_key_agreement(uint8_t *ws);
void penumbra_audit_spend_auth_sign(uint8_t *ws);
-static uint64_t state = 0x9e3779b97f4a7c15ULL;
+static uint64_t secrets = 0x9e3779b97f4a7c15ULL;
+static uint64_t publics = 0x0123456789abcdefULL;
-static uint64_t splitmix(void) {
- uint64_t z = (state += 0x9e3779b97f4a7c15ULL);
+static uint64_t splitmix(uint64_t *state) {
+ uint64_t z = (*state += 0x9e3779b97f4a7c15ULL);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
-static void fill(uint8_t *p, size_t n) {
- for (size_t i = 0; i < n; i++) p[i] = (uint8_t)splitmix();
+static void fill(uint64_t *state, uint8_t *p, size_t n) {
+ for (size_t i = 0; i < n; i++) p[i] = (uint8_t)splitmix(state);
}
/* a canonical scalar: random little-endian bytes with the top byte
* cleared, below the decaf377 scalar modulus */
-static void scalar(uint8_t *p) {
- fill(p, 32);
+static void scalar(uint64_t *state, uint8_t *p) {
+ fill(state, p, 32);
p[31] = 0;
}
static void public_key(void) {
uint8_t ws[64];
- scalar(ws);
+ scalar(&secrets, ws);
vestigia_secret(ws, 32);
penumbra_audit_public_key(ws);
vestigia_public(ws + 32, 32);
@@ -48,9 +52,9 @@ static void public_key(void) {
static void key_agreement(void) {
uint8_t peer[64];
uint8_t ws[96];
- scalar(peer);
+ scalar(&publics, peer);
penumbra_audit_public_key(peer);
- scalar(ws);
+ scalar(&secrets, ws);
memcpy(ws + 32, peer + 32, 32);
vestigia_secret(ws, 32);
penumbra_audit_key_agreement(ws);
@@ -58,9 +62,9 @@ static void key_agreement(void) {
static void spend_auth_sign(void) {
uint8_t ws[208];
- scalar(ws);
- fill(ws + 32, 80);
- fill(ws + 112, 32);
+ scalar(&secrets, ws);
+ fill(&secrets, ws + 32, 80);
+ fill(&publics, ws + 112, 32);
/* the key and the signing randomness are secret; the message is
* public */
vestigia_secret(ws, 112);
@@ -74,6 +78,7 @@ int main(int argc, char **argv) {
return 2;
}
int runs = argc > 2 ? atoi(argv[2]) : 4;
+ if (argc > 3) secrets = strtoull(argv[3], NULL, 16);
void (*root)(void) = NULL;
if (strcmp(argv[1], "public_key") == 0) root = public_key;
else if (strcmp(argv[1], "key_agreement") == 0) root = key_agreement;
diff --git a/flake.nix b/flake.nix
@@ -26,6 +26,25 @@
linux = pkgs.stdenv.hostPlatform.isLinux;
valgrind = pkgs.valgrind;
+ # the QEMU plugin recording a run's leakage trace per
+ # instruction, and the QEMU that runs a harness of this
+ # system's ISA under it
+ qemu = pkgs.qemu;
+ qemuFor = {
+ x86_64 = "${qemu}/bin/qemu-x86_64";
+ aarch64 = "${qemu}/bin/qemu-aarch64";
+ };
+ plugin = pkgs.runCommandCC "vestigia-qemu-plugin" {
+ nativeBuildInputs = [ pkgs.pkg-config ];
+ buildInputs = [ pkgs.glib ];
+ } ''
+ mkdir -p $out/lib
+ cc -O2 -shared -fPIC -Wall -Werror \
+ $(pkg-config --cflags glib-2.0) -I${qemu}/include \
+ -o $out/lib/libvestigia-qemu.so ${./plugin/vestigia-qemu.c}
+ '';
+ isa = builtins.head (lib.splitString "-" system);
+
# the harness-side header; a harness build also needs
# valgrind's own (valgrindDev)
include = pkgs.runCommand "vestigia-include" { } ''
@@ -39,8 +58,14 @@
} ''
mkdir -p $out/bin
makeWrapper ${hpkgs.vestigia}/bin/vestigia $out/bin/vestigia \
- ${lib.optionalString linux
- "--set-default VESTIGIA_VALGRIND ${valgrind}/bin/valgrind"}
+ ${lib.optionalString linux (lib.concatStringsSep " " [
+ "--set-default VESTIGIA_VALGRIND ${valgrind}/bin/valgrind"
+ "--set-default VESTIGIA_QEMU ${qemuFor.${isa}}"
+ "--set-default VESTIGIA_PLUGIN"
+ "${plugin}/lib/libvestigia-qemu.so"
+ "--set-default VESTIGIA_ADDR2LINE"
+ "${pkgs.binutils-unwrapped}/bin/addr2line"
+ ])}
ln -s ${include}/include $out/include
'';
@@ -51,6 +76,7 @@
traceOf = { name, harness, args ? [ ] }:
pkgs.runCommand "vestigia-trace-${name}" { } ''
mkdir -p $out
+ start=$(date +%s%N)
set +e
${vestigia}/bin/vestigia run \
--xml $out/memcheck.xml --out $out/trace.json \
@@ -58,18 +84,45 @@
> $out/stdout 2> $out/stderr
echo $? > $out/status
set -e
+ echo $(( ($(date +%s%N) - start) / 1000000 )) > $out/milliseconds
test -s $out/trace.json || {
cat $out/stderr >&2
exit 1
}
'';
+
+ # runs of one harness that differ only in a secret, each
+ # recorded under QEMU, and where they diverge: the dumps, and
+ # the report. `runs` is a list of argument lists; `objects`
+ # keeps origins in objects whose path contains one of them.
+ # A run's own failure leaves its status; a dump vestigia
+ # cannot read fails the build.
+ diffOf = { name, harness, runs, objects ? [ ] }:
+ pkgs.runCommand "vestigia-diff-${name}" { } ''
+ mkdir -p $out
+ start=$(date +%s%N)
+ ${lib.concatImapStrings (k: args: ''
+ set +e
+ ${vestigia}/bin/vestigia record --dump $out/dump-${toString k} \
+ -- ${harness} ${lib.escapeShellArgs args} \
+ > $out/stdout-${toString k} 2> $out/stderr-${toString k}
+ echo $? > $out/status-${toString k}
+ set -e
+ '') runs}
+ ${vestigia}/bin/vestigia diff --out $out/diff.json \
+ ${lib.concatMapStrings (o: "--object ${lib.escapeShellArg o} ")
+ objects} \
+ $out/dump-* 2> $out/summary
+ echo $(( ($(date +%s%N) - start) / 1000000 )) > $out/milliseconds
+ '';
in
{
packages.default = vestigia;
packages.include = include;
+ packages.plugin = plugin;
lib = {
- inherit traceOf;
+ inherit traceOf diffOf;
valgrindDev = valgrind.dev;
};
diff --git a/lib/Vestigia/Diff.hs b/lib/Vestigia/Diff.hs
@@ -0,0 +1,253 @@
+{-# OPTIONS_HADDOCK prune #-}
+{-# LANGUAGE OverloadedStrings #-}
+
+-- |
+-- Module: Vestigia.Diff
+-- Copyright: (c) 2026 Jared Tobin
+-- License: MIT
+-- Maintainer: Jared Tobin <jared@ppad.tech>
+--
+-- 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.
+--
+-- A branch whose outcome did not depend on the secret takes each
+-- of its transfers in the same proportion however often it runs; a
+-- branch whose outcomes differ in proportion between runs had its
+-- own condition depend on the secret, and is a `control` origin
+-- (a loop whose trip count the secret sets is one, though it also
+-- runs a different number of times). 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, and is counted rather than listed.
+--
+-- Unlike memcheck's taint, this sees what control flow does to
+-- data as well as what data does: a value chosen by a secret
+-- branch and then used as an index differs between runs, though
+-- no undefined bit ever reached it. It sees only what the chosen
+-- secrets actually varied.
+
+module Vestigia.Diff (
+ Insn(..)
+ , Dump(..)
+ , readDump
+ , Origin(..)
+ , Divergence(..)
+ , diffDumps
+ , restrictTo
+ , divergenceJson
+ , divergenceSummary
+ ) where
+
+import qualified Data.List as L
+import qualified Data.Map.Strict as M
+import qualified Data.Set as S
+import qualified Data.Text as T
+import Numeric (readHex, showHex)
+
+import Vestigia.Json
+import Vestigia.Symbol (Place(..))
+
+-- | One instruction of a run.
+data Insn = Insn {
+ inPc :: !Integer
+ , inCount :: !Integer
+ , inAccesses :: !Integer
+ , inFingerprint :: !T.Text
+ , inObject :: !(Maybe T.Text)
+ , inOffset :: !Integer
+ } deriving (Eq, Show)
+
+-- | One run: its instructions by address, and its transfers by
+-- source, each a count per target.
+data Dump = Dump {
+ dpInsns :: !(M.Map Integer Insn)
+ , dpTransfers :: !(M.Map Integer (M.Map Integer Integer))
+ } deriving (Eq, Show)
+
+-- | Read a plugin dump.
+readDump :: T.Text -> Either String Dump
+readDump t = go (T.lines t) M.empty M.empty
+ where
+ go ls is es = case ls of
+ [] -> pure (Dump is es)
+ (l : rest) -> case T.words l of
+ [ "I", pc, n, a, fp, obj, off ] -> do
+ i <- Insn <$> unhex pc <*> unhex n <*> unhex a <*> pure fp
+ <*> pure (if obj == "-" then Nothing else Just obj)
+ <*> unhex off
+ go rest (M.insert (inPc i) i is) es
+ [ "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)
+ [] -> go rest is es
+ _ -> Left ("an unreadable dump line: " <> T.unpack l)
+ unhex x = case readHex (T.unpack x) of
+ [ (v, "") ] -> pure v
+ _ -> Left ("not hexadecimal: " <> T.unpack x)
+
+-- | How an origin depended on the secret.
+data Origin =
+ ControlOrigin
+ | AddressOrigin
+ deriving (Eq, Ord, Show)
+
+-- | Where the runs differ: the origins, each an instruction run
+-- equally often everywhere, and how many instructions ran a
+-- different number of times.
+data Divergence = Divergence {
+ dvOrigins :: ![(Origin, Insn)]
+ , dvDownstream :: ![Insn]
+ , dvRuns :: !Int
+ } deriving (Eq, Show)
+
+-- | Compare runs. Every run is set against every other, so an
+-- origin is any instruction at which some two runs differ.
+diffDumps :: [Dump] -> Divergence
+diffDumps ds = Divergence {
+ dvOrigins = L.sortOn (inPc . snd) (controls <> addresses)
+ , dvDownstream = [ i | pc <- S.toAscList downstream
+ , Just i <- [ firstInsn pc ] ]
+ , dvRuns = length ds
+ }
+ where
+ pcs = S.unions (fmap (M.keysSet . dpInsns) ds)
+ firstInsn pc = case [ i | d <- ds
+ , Just i <- [ M.lookup pc (dpInsns d) ] ] of
+ (i : _) -> Just i
+ [] -> Nothing
+
+ -- run counts per run, absent counted as never run
+ countsAt pc = [ maybe 0 inCount (M.lookup pc (dpInsns d)) | d <- ds ]
+ alike xs = case xs of
+ [] -> True
+ (x : rest) -> all (== x) rest
+
+ steady = S.filter (alike . countsAt) pcs
+
+ -- an instruction's run count and transfers, in each run that ran
+ -- it
+ ranAt pc =
+ [ (inCount i, M.findWithDefault M.empty pc (dpTransfers d))
+ | d <- ds, Just i <- [ M.lookup pc (dpInsns d) ], inCount i > 0 ]
+ transferSources = S.unions (fmap (M.keysSet . dpTransfers) ds)
+
+ -- outcomes in the same proportion: each target taken as often,
+ -- relative to the run count, in both
+ proportional (c, ts) (c', ts') =
+ M.keysSet ts == M.keysSet ts'
+ && and (M.elems (M.intersectionWith (\e e' -> e * c' == e' * c)
+ ts ts'))
+ divergent pc = case ranAt pc of
+ (r : rest) -> not (all (proportional r) rest)
+ [] -> False
+
+ controlPcs = S.filter divergent transferSources
+ downstream = (pcs `S.difference` steady) `S.difference` controlPcs
+
+ controls =
+ [ (ControlOrigin, i)
+ | pc <- S.toAscList controlPcs
+ , Just i <- [ firstInsn pc ] ]
+
+ addresses =
+ [ (AddressOrigin, i)
+ | pc <- S.toAscList steady
+ , let fps = [ fmap inFingerprint (M.lookup pc (dpInsns d))
+ | d <- ds ]
+ , not (alike fps)
+ , Just i <- [ firstInsn pc ]
+ , inAccesses i > 0 ]
+
+-- | Only the origins in objects whose path contains one of the
+-- given texts; downstream instructions are kept, to be counted.
+restrictTo :: [T.Text] -> Divergence -> Divergence
+restrictTo ps dv
+ | null ps = dv
+ | otherwise = dv { dvOrigins = filter (inside . snd) (dvOrigins dv) }
+ where
+ inside i = case inObject i of
+ Just o -> any (`T.isInfixOf` o) ps
+ Nothing -> False
+
+originText :: Origin -> T.Text
+originText o = case o of
+ ControlOrigin -> "control"
+ AddressOrigin -> "address"
+
+-- | The report: @vestigia/diff-v1@.
+divergenceJson
+ :: T.Text -> M.Map (T.Text, Integer) [Place] -> Divergence -> Value
+divergenceJson version places dv = Object
+ [ ("schema", String "vestigia/diff-v1")
+ , ("tool", Object [ ("name", String "vestigia")
+ , ("version", String version) ])
+ , ("runs", Number (toInteger (dvRuns dv)))
+ , ("summary", Object
+ [ ("control", count ControlOrigin)
+ , ("address", count AddressOrigin)
+ , ("downstream", Number (toInteger (length (dvDownstream dv))))
+ ])
+ , ("origins", Array
+ [ Object $
+ [ ("class", String (originText o))
+ , ("pc", String (hex (inPc i)))
+ , ("object", maybe Null String (inObject i))
+ , ("offset", String (hex (inOffset i)))
+ , ("count", Number (inCount i))
+ , ("frames", Array (fmap placeJson (placesOf i)))
+ ]
+ | (o, i) <- dvOrigins dv ])
+ , ("downstream", Object
+ [ (o, Number (toInteger n))
+ | (o, n) <- M.toList (M.fromListWith (+)
+ [ (maybe "-" id (inObject i), 1 :: Int)
+ | i <- dvDownstream dv ]) ])
+ ]
+ where
+ count o = Number (toInteger (length
+ [ () | (o', _) <- dvOrigins dv, o' == o ]))
+ placesOf i = case inObject i of
+ Just obj -> M.findWithDefault [] (obj, inOffset i) places
+ Nothing -> []
+ placeJson p = Object
+ [ ("function", maybe Null String (plFunction p))
+ , ("file", maybe Null String (plFile p))
+ , ("line", maybe Null (Number . toInteger) (plLine p))
+ ]
+
+-- | One line per origin, innermost frame first, for a terminal.
+divergenceSummary
+ :: M.Map (T.Text, Integer) [Place] -> Divergence -> T.Text
+divergenceSummary places dv = T.unlines $
+ [ T.intercalate " "
+ [ originText o
+ , hex (inOffset i)
+ , maybe "?" id (plFunction =<< innermost i)
+ , maybe "?" location (innermost i)
+ , maybe "-" base (inObject i) ]
+ | (o, i) <- dvOrigins dv ]
+ <> [ T.pack (show (length (dvOrigins dv))) <> " origin(s) over "
+ <> T.pack (show (dvRuns dv)) <> " run(s); "
+ <> T.pack (show (length (dvDownstream dv)))
+ <> " instruction(s) downstream" ]
+ where
+ innermost i = case inObject i of
+ Just obj -> case M.findWithDefault [] (obj, inOffset i) places of
+ (p : _) -> Just p
+ [] -> Nothing
+ Nothing -> Nothing
+ location p = case (plFile p, plLine p) of
+ (Just f, Just l) -> base f <> ":" <> T.pack (show l)
+ (Just f, Nothing) -> base f
+ _ -> "?"
+ base p = case reverse (T.splitOn "/" p) of
+ (x : _) -> x
+ [] -> p
+
+hex :: Integer -> T.Text
+hex n = "0x" <> T.pack (showHex n "")
diff --git a/lib/Vestigia/Symbol.hs b/lib/Vestigia/Symbol.hs
@@ -0,0 +1,100 @@
+{-# OPTIONS_HADDOCK prune #-}
+{-# LANGUAGE OverloadedStrings #-}
+
+-- |
+-- Module: Vestigia.Symbol
+-- Copyright: (c) 2026 Jared Tobin
+-- License: MIT
+-- Maintainer: Jared Tobin <jared@ppad.tech>
+--
+-- Naming an instruction by its source: binutils' addr2line over an
+-- object's debug information, inlined frames included. An object's
+-- file offset is taken as its virtual address, which holds for the
+-- executable segments of what GNU ld and lld emit; an object that
+-- does not satisfy it names its sites wrongly, not silently: its
+-- functions will not match its disassembly.
+
+module Vestigia.Symbol (
+ Place(..)
+ , symbolize
+ , parseAddr2line
+ ) where
+
+import Control.Exception (IOException, try)
+import qualified Data.Map.Strict as M
+import qualified Data.Text as T
+import Numeric (readHex, showHex)
+import System.Process (readProcess)
+import Text.Read (readMaybe)
+
+-- | One frame of a source location: the function and, where the
+-- debug information has it, the file and line. The innermost
+-- frame comes first.
+data Place = Place {
+ plFunction :: !(Maybe T.Text)
+ , plFile :: !(Maybe T.Text)
+ , plLine :: !(Maybe Int)
+ } deriving (Eq, Show)
+
+-- | The source of each offset, per object, by one addr2line call
+-- per object. An object addr2line cannot read names nothing.
+symbolize
+ :: FilePath -> [(T.Text, Integer)]
+ -> IO (M.Map (T.Text, Integer) [Place])
+symbolize addr2line keys = do
+ let byObject = M.fromListWith (<>) [ (o, [ off ]) | (o, off) <- keys ]
+ parts <- traverse one (M.toList byObject)
+ pure (M.unions parts)
+ where
+ one (obj, offs) = do
+ r <- try (readProcess addr2line
+ [ "-a", "-f", "-i", "-C", "-e", T.unpack obj ]
+ (unlines [ "0x" <> showHex o "" | o <- offs ]))
+ :: IO (Either IOException String)
+ pure $ case r of
+ Left _ -> M.empty
+ Right out -> M.fromList
+ [ ((obj, a), ps) | (a, ps) <- parseAddr2line (T.pack out) ]
+
+-- | addr2line's output under @-a -f -i@: an address line, then a
+-- function line and a location line per frame.
+--
+-- >>> parseAddr2line "0x20\n??\n??:0\n"
+-- [(32,[Place Nothing Nothing Nothing])]
+parseAddr2line :: T.Text -> [(Integer, [Place])]
+parseAddr2line = go . T.lines
+ where
+ go ls = case ls of
+ (a : rest) | Just addr <- address a ->
+ let (body, more) = break (\l -> address l /= Nothing) rest
+ in (addr, frames body) : go more
+ (_ : rest) -> go rest
+ [] -> []
+
+ address :: T.Text -> Maybe Integer
+ address l = case T.stripPrefix "0x" l of
+ Just h | not (T.null h), [ (v, "") ] <- readHex (T.unpack h) ->
+ Just v
+ _ -> Nothing
+
+ frames ls = case ls of
+ (f : loc : rest) -> place f loc : frames rest
+ _ -> []
+
+ place f loc =
+ let (file, line) = location loc
+ in Place {
+ plFunction = if f == "??" then Nothing else Just f
+ , plFile = file
+ , plLine = line
+ }
+
+ -- "path:line", "path:line (discriminator n)", or "??:0"
+ location loc =
+ let l = T.takeWhile (/= ' ') loc
+ (p, n) = T.breakOnEnd ":" l
+ path = T.dropEnd 1 p
+ in ( if T.null path || path == "??" then Nothing else Just path
+ , case readMaybe (T.unpack n) of
+ Just 0 -> Nothing
+ other -> other )
diff --git a/plugin/vestigia-qemu.c b/plugin/vestigia-qemu.c
@@ -0,0 +1,203 @@
+/*
+ * vestigia-qemu.c: a QEMU user-mode plugin recording a run's leakage
+ * trace, summarised per instruction.
+ *
+ * Copyright (c) 2026 Jared Tobin
+ * License: MIT
+ *
+ * For every guest instruction executed it records how many times it
+ * ran, every non-sequential transfer out of it (a branch taken, a
+ * call, a jump, a return) with its count, and an order-sensitive
+ * fingerprint of the data addresses it touched. Two runs of a
+ * program that differ only in a secret then differ exactly where
+ * the execution depended on the secret: a transfer whose counts
+ * differ is a secret-dependent branch, 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.
+ *
+ * At exit it writes, to the file named by its `out` argument:
+ *
+ * I <pc> <count> <accesses> <fingerprint> <object> <offset>
+ * E <from> <to> <count>
+ *
+ * in hex, where <object> is the file the instruction's bytes were
+ * mapped from ("-" if none) and <offset> its offset in that file.
+ *
+ * A single-threaded guest is assumed: the state below is unlocked.
+ */
+#include <glib.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <qemu-plugin.h>
+
+QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
+
+typedef struct Insn {
+ uint64_t pc;
+ uint64_t size;
+ uintptr_t haddr;
+ uint64_t count;
+ uint64_t accesses;
+ uint64_t fingerprint;
+ GHashTable *succ; /* target pc -> count, for transfers */
+} Insn;
+
+static GHashTable *insns; /* pc -> Insn */
+static Insn *prev; /* the instruction executed last */
+static char *out_path;
+
+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) {
+ 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->fingerprint = 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);
+ }
+ return i;
+}
+
+static void transfer(Insn *from, uint64_t to) {
+ uint64_t *n = g_hash_table_lookup(from->succ, &to);
+ if (n == NULL) {
+ uint64_t *k = g_new(uint64_t, 1);
+ *k = to;
+ n = g_new0(uint64_t, 1);
+ g_hash_table_insert(from->succ, k, n);
+ }
+ (*n)++;
+}
+
+static void on_exec(unsigned int vcpu, void *udata) {
+ Insn *i = udata;
+ (void)vcpu;
+ if (prev != NULL && i->pc != prev->pc + prev->size)
+ transfer(prev, i->pc);
+ prev = i;
+ i->count++;
+}
+
+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++;
+}
+
+static void on_translate(qemu_plugin_id_t id, struct qemu_plugin_tb *tb) {
+ size_t n = qemu_plugin_tb_n_insns(tb);
+ (void)id;
+ for (size_t k = 0; k < n; k++) {
+ struct qemu_plugin_insn *qi = qemu_plugin_tb_get_insn(tb, k);
+ Insn *i = insn_at(qemu_plugin_insn_vaddr(qi),
+ qemu_plugin_insn_size(qi),
+ (uintptr_t)qemu_plugin_insn_haddr(qi));
+ 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,
+ QEMU_PLUGIN_MEM_RW, i);
+ }
+}
+
+/* the host's file-backed mappings, for naming an instruction's file */
+typedef struct Region {
+ uintptr_t start, end;
+ uint64_t offset;
+ char *path;
+} Region;
+
+static GArray *read_maps(void) {
+ GArray *rs = g_array_new(FALSE, FALSE, sizeof(Region));
+ FILE *f = fopen("/proc/self/maps", "r");
+ char line[4096];
+ if (f == NULL) return rs;
+ while (fgets(line, sizeof line, f) != NULL) {
+ uintptr_t start, end;
+ uint64_t offset;
+ char perms[8], dev[16];
+ unsigned long inode;
+ int used = 0;
+ if (sscanf(line, "%" SCNxPTR "-%" SCNxPTR " %7s %" SCNx64
+ " %15s %lu %n", &start, &end, perms, &offset, dev,
+ &inode, &used) < 6)
+ continue;
+ char *path = line + used;
+ path[strcspn(path, "\n")] = '\0';
+ if (inode == 0 || path[0] != '/') continue;
+ Region r = { start, end, offset, g_strdup(path) };
+ g_array_append_val(rs, r);
+ }
+ fclose(f);
+ return rs;
+}
+
+static const Region *region_of(GArray *rs, uintptr_t a) {
+ for (guint k = 0; k < rs->len; k++) {
+ const Region *r = &g_array_index(rs, Region, k);
+ if (a >= r->start && a < r->end) return r;
+ }
+ return NULL;
+}
+
+static void at_exit(qemu_plugin_id_t id, void *p) {
+ (void)id;
+ (void)p;
+ FILE *out = fopen(out_path, "w");
+ if (out == NULL) {
+ fprintf(stderr, "vestigia-qemu: cannot write %s\n", out_path);
+ return;
+ }
+ GArray *rs = read_maps();
+ GHashTableIter it;
+ gpointer key, val;
+ g_hash_table_iter_init(&it, insns);
+ while (g_hash_table_iter_next(&it, &key, &val)) {
+ Insn *i = val;
+ const Region *r = region_of(rs, i->haddr);
+ if (r != NULL)
+ fprintf(out, "I %" PRIx64 " %" PRIx64 " %" PRIx64 " %016" PRIx64
+ " %s %" PRIx64 "\n", i->pc, i->count, i->accesses,
+ i->fingerprint, r->path,
+ (uint64_t)(i->haddr - r->start) + r->offset);
+ else
+ fprintf(out, "I %" PRIx64 " %" PRIx64 " %" PRIx64 " %016" PRIx64
+ " - 0\n", i->pc, i->count, i->accesses, i->fingerprint);
+ GHashTableIter jt;
+ gpointer tk, tn;
+ g_hash_table_iter_init(&jt, i->succ);
+ while (g_hash_table_iter_next(&jt, &tk, &tn))
+ fprintf(out, "E %" PRIx64 " %" PRIx64 " %" PRIx64 "\n", i->pc,
+ *(uint64_t *)tk, *(uint64_t *)tn);
+ }
+ fclose(out);
+}
+
+QEMU_PLUGIN_EXPORT int qemu_plugin_install(qemu_plugin_id_t id,
+ const qemu_info_t *info,
+ int argc, char **argv) {
+ (void)info;
+ for (int k = 0; k < argc; k++)
+ if (strncmp(argv[k], "out=", 4) == 0)
+ out_path = g_strdup(argv[k] + 4);
+ if (out_path == NULL) {
+ fprintf(stderr, "vestigia-qemu: an out=FILE argument is needed\n");
+ return -1;
+ }
+ insns = g_hash_table_new(g_int64_hash, g_int64_equal);
+ qemu_plugin_register_vcpu_tb_trans_cb(id, on_translate);
+ qemu_plugin_register_atexit_cb(id, at_exit, NULL);
+ return 0;
+}
diff --git a/test/Main.hs b/test/Main.hs
@@ -5,13 +5,16 @@ module Main (
) where
import qualified Data.ByteString as BS
+import qualified Data.Map.Strict as M
import qualified Data.Text as T
import qualified Data.Text.Encoding as TE
import Test.Tasty
import Test.Tasty.HUnit
+import Vestigia.Diff
import Vestigia.Json
import Vestigia.Memcheck
+import Vestigia.Symbol
import Vestigia.Trace
import Vestigia.Xml
@@ -20,6 +23,8 @@ main = defaultMain $ testGroup "vestigia"
[ xmlTests
, memcheckTests
, traceTests
+ , diffTests
+ , symbolTests
, jsonTests
]
@@ -96,6 +101,83 @@ traceTests = testGroup "trace"
@?= [ (0x10, 7, 2) ]
]
+diffTests :: TestTree
+diffTests = testGroup "diff"
+ [ testCase "a dump reads whole" $ do
+ d <- either assertFailure pure (readDump dumpA)
+ fmap inCount (dpInsns d) @?= M.fromList
+ [ (0x10, 4), (0x20, 4), (0x30, 2), (0x40, 1) ]
+ M.lookup 0x10 (fmap inObject (dpInsns d)) @?= Just (Just "/lib.so")
+ dpTransfers d @?= M.fromList
+ [ (0x10, M.fromList [ (0x30, 2) ]) ]
+
+ , testCase "origins are where steady instructions differ" $ do
+ a <- either assertFailure pure (readDump dumpA)
+ b <- either assertFailure pure (readDump dumpB)
+ let dv = diffDumps [ a, b ]
+ fmap (\(o, i) -> (o, inPc i)) (dvOrigins dv)
+ @?= [ (ControlOrigin, 0x10), (AddressOrigin, 0x20) ]
+ fmap inPc (dvDownstream dv) @?= [ 0x30 ]
+
+ , testCase "a loop the secret sets is an origin" $ do
+ a <- either assertFailure pure (readDump loopA)
+ b <- either assertFailure pure (readDump loopB)
+ let dv = diffDumps [ a, b ]
+ fmap (\(o, i) -> (o, inPc i)) (dvOrigins dv)
+ @?= [ (ControlOrigin, 0x10) ]
+ fmap inPc (dvDownstream dv) @?= [ 0x14, 0x18 ]
+
+ , testCase "a branch downstream, always taken, is no origin" $ do
+ a <- either assertFailure pure (readDump loopA)
+ b <- either assertFailure pure (readDump loopB)
+ let dv = diffDumps [ a, b ]
+ notElem 0x18 (fmap (inPc . snd) (dvOrigins dv))
+ @? "a branch that always jumps is not secret-dependent"
+
+ , testCase "identical runs have no origins" $ do
+ a <- either assertFailure pure (readDump dumpA)
+ let dv = diffDumps [ a, a ]
+ dvOrigins dv @?= []
+ dvDownstream dv @?= []
+
+ , testCase "an unreadable line is refused" $
+ isLeft (readDump "I 10 zz 0 f /lib.so 0\n") @? "accepted"
+ ]
+ where
+ -- 0x10 is a branch run four times, taken twice in A and three
+ -- times in B; 0x20 reads other addresses in B; 0x30, inside the
+ -- branch, runs a different number of times; 0x40 is the same
+ dumpA = T.unlines
+ [ "I 10 4 0 aaaa /lib.so 10", "E 10 30 2"
+ , "I 20 4 4 bbbb /lib.so 20", "I 30 2 0 cccc /lib.so 30"
+ , "I 40 1 1 dddd /lib.so 40" ]
+ dumpB = T.unlines
+ [ "I 10 4 0 aaaa /lib.so 10", "E 10 30 3"
+ , "I 20 4 4 eeee /lib.so 20", "I 30 3 0 cccc /lib.so 30"
+ , "I 40 1 1 dddd /lib.so 40" ]
+ -- a loop at 0x10 the secret runs 5 or 9 times, its back edge to
+ -- 0x14 taken every time but the last; 0x18, in the body, always
+ -- jumps back to 0x10
+ loopA = T.unlines
+ [ "I 10 5 0 aaaa /lib.so 10", "E 10 14 4"
+ , "I 14 4 0 bbbb /lib.so 14"
+ , "I 18 4 0 cccc /lib.so 18", "E 18 10 4" ]
+ loopB = T.unlines
+ [ "I 10 9 0 aaaa /lib.so 10", "E 10 14 8"
+ , "I 14 8 0 bbbb /lib.so 14"
+ , "I 18 8 0 cccc /lib.so 18", "E 18 10 8" ]
+
+symbolTests :: TestTree
+symbolTests = testGroup "symbol"
+ [ testCase "addr2line's inlined frames and discriminators" $
+ parseAddr2line (T.unlines
+ [ "0x0000000000001234", "inner", "/src/a.rs:12 (discriminator 3)"
+ , "outer", "/src/b.rs:40", "0x0000000000005678", "??", "??:0" ])
+ @?= [ (0x1234, [ Place (Just "inner") (Just "/src/a.rs") (Just 12)
+ , Place (Just "outer") (Just "/src/b.rs") (Just 40) ])
+ , (0x5678, [ Place Nothing Nothing Nothing ]) ]
+ ]
+
jsonTests :: TestTree
jsonTests = testGroup "json"
[ testCase "objects keep their order and strings escape" $
diff --git a/vestigia.cabal b/vestigia.cabal
@@ -27,13 +27,16 @@ library
ghc-options:
-Wall -Werror
exposed-modules:
- Vestigia.Json
+ Vestigia.Diff
+ , Vestigia.Json
, Vestigia.Memcheck
+ , Vestigia.Symbol
, Vestigia.Trace
, Vestigia.Xml
build-depends:
base >= 4.9 && < 5
, containers
+ , process
, text
executable vestigia
@@ -64,6 +67,7 @@ test-suite vestigia-tests
build-depends:
base
, bytestring
+ , containers
, tasty
, tasty-hunit
, text
