commit 806a148127eee54b9b2fc5f7e3f68e3147300439
parent 5ee48803f1f90d28d65229525953692310b59771
Author: Jared Tobin <jared@jtobin.io>
Date: Wed, 21 Oct 2026 10:41:07 +0400
diff: each origin with the calls that reached it
memcheck gives a site its callers, out to the root, but an origin the
differential trace alone saw (one downstream of a secret branch, which
memcheck's taint does not follow) had only the inline chain at its
own address, so a reader of it saw the function it was in and not
who called that.
The plugin now marks calls too (x86_64's CALL rel32 and CALL r/m,
aarch64's BL, BLR, and their authenticated forms) and keeps a shadow
stack of the calls in progress: a call pushes its return address and
enters the context made by it in the current one; a return pops to
the innermost call returning where it went, and leaves the stack as
it is where none does. Each instruction that could be an origin (one
ending a translation block, as every branch does, one touching
memory, or a division) keeps the contexts it ran in, sixteen at most,
saying where it ran in more; a call site caches the context it last
made, and an instruction past its sixteen stops looking. The dump
gives the contexts (C lines) and each instruction's (K lines).
diff resolves an origin's contexts in the declared and designed runs
into chains of calls, each named by its object and address there (24
at most, as memcheck keeps), and reports their distinct chains,
sixteen at most, as the origin's `stacks`: its own frames then each
call's, innermost first, each frame with the object and address it
names, as a taint report's stacks are, beside `partial` where more
were seen. GHC calls by jumping, so a GHC origin's stack is its own
frames alone.
On pollux Penumbra's origins reach out to main through the audited
library (hashbrown's get_inner through sqrt_ratio_zeta and
vartime_compress to public_key), and a root's diff takes about a
quarter longer. The probe check holds each origin's stack, on x86_64
and aarch64, to the call in main that reached it.
Diffstat:
8 files changed, 316 insertions(+), 60 deletions(-)
diff --git a/CHANGELOG b/CHANGELOG
@@ -20,8 +20,9 @@
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, an integer division on other
- operands an `operand` origin, and what ran downstream listed
- per object), set against controls repeating a secret, with
+ operands an `operand` origin, each origin with the calls that
+ reached it, 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`);
diff --git a/README.md b/README.md
@@ -84,7 +84,8 @@ An *origin* is a branch whose outcomes differ between runs, in
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
+behaved alike there, and the calls that reached it, kept by the
+plugin as a shadow stack, as memcheck gives a site's callers. 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.
diff --git a/app/Main.hs b/app/Main.hs
@@ -17,6 +17,7 @@ import Control.Exception (IOException, try)
import Control.Monad (unless, when)
import qualified Data.ByteString as BS
import Data.Char (toUpper)
+import qualified Data.Map.Strict as M
import Data.Foldable (for_)
import Data.Version (showVersion)
import qualified GHC.Foreign as GF
@@ -41,8 +42,8 @@ import qualified System.Process as P
import Paths_vestigia (version)
import Vestigia.Diff
(Dump(..), Kind(..), Named(..), Run(..), diffDesigned, divergenceJson,
- divergenceSummary, dvOrigins, inObject, inOffset, layoutApart,
- readDump, restrictTo, runApart)
+ divergenceSummary, dvCallers, dvOrigins, inObject, inOffset, inPc,
+ layoutApart, readDump, restrictTo, runApart)
import Vestigia.Json (encode)
import Vestigia.Layout (fixLayout)
import Vestigia.Memcheck (Memcheck, readMemcheck)
@@ -423,9 +424,13 @@ diff o paths = do
[] -> pure ()
let dv = restrictTo (oObjects o)
(diffDesigned controls dumps designed)
- places <- symbolize addr2line
+ places <- symbolize addr2line $
[ (obj, inOffset i) | (_, i) <- dvOrigins dv
, Just obj <- [ inObject i ] ]
+ -- the calls that reached each origin
+ <> [ (obj, a) | (_, i) <- dvOrigins dv
+ , Just (stacks, _) <- [ M.lookup (inPc i) (dvCallers dv) ]
+ , calls <- stacks, (Just obj, a) <- calls ]
let doc = encode (divergenceJson (T.pack (showVersion version))
(fmap snd named) places dv)
maybe (TIO.putStr doc) (\p -> TIO.writeFile p doc) (oOut o)
diff --git a/lib/Vestigia/Diff.hs b/lib/Vestigia/Diff.hs
@@ -69,6 +69,7 @@ module Vestigia.Diff (
, Run(..)
, Dump(..)
, readDump
+ , callsOf
, runApart
, Kind(..)
, Named(..)
@@ -84,6 +85,7 @@ module Vestigia.Diff (
, divergenceSummary
) where
+import Control.Monad (foldM, unless)
import qualified Data.ByteString as BS
import qualified Data.List as L
import qualified Data.Map.Strict as M
@@ -122,13 +124,18 @@ data Run = Run {
-- | One run: its instructions by address, its transfers by source,
-- each a count per target, the instructions that return, the
--- divisions' operands, fingerprinted, and how it was made, where
--- its dump says.
+-- divisions' operands, fingerprinted, the contexts calls made (each
+-- by the context it was made in and the call's address, 0 being
+-- the program's own), the contexts each instruction ran in (with
+-- whether it ran in more than the plugin kept), and how the run
+-- 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)
+ , dpContexts :: !(M.Map Integer (Integer, Integer))
+ , dpCallers :: !(M.Map Integer (Bool, [Integer]))
, dpRun :: !(Maybe Run)
} deriving (Eq, Show)
@@ -136,54 +143,79 @@ data Dump = Dump {
-- no run (the plugin writes every instruction the guest executed),
-- and is refused rather than compared as one that did nothing, as
-- is the dump of a guest the plugin stopped for starting a second
--- thread. The record `vestigia record` appends (an @A@ line per
--- argument, its bytes in hex; @N@, the environment's variables and
--- bytes, in hex; @X@, the exit status, in decimal) is read whole or
--- not at all.
+-- thread, or one whose contexts do not chain back to the
+-- program's own. The record `vestigia record` appends (an @A@ line
+-- per argument, its bytes in hex; @N@, the environment's variables
+-- and 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 M.empty [] Nothing Nothing
+readDump t = do
+ d <- foldM line (Dump M.empty M.empty S.empty M.empty M.empty M.empty
+ Nothing, [], Nothing, Nothing) (T.lines t)
+ let (dump, as, env, st) = d
+ cx = dpContexts dump
+ unless (any ((> 0) . inCount) (M.elems (dpInsns dump))) $
+ Left "no instruction ran: the run was not recorded"
+ -- each context made in one made before it, so that its calls end
+ unless (and [ c' < c && (c' == 0 || M.member c' cx)
+ | (c, (c', _)) <- M.toList cx ]) $
+ Left "a context made in one not made before it"
+ unless (and [ c == 0 || M.member c cx
+ | (_, cs) <- M.elems (dpCallers dump), c <- cs ]) $
+ Left "an instruction run in a context the dump does not make"
+ r <- record (reverse as) env st
+ pure dump { dpRun = r }
where
- go ls is es rs ds as env st = case ls of
- []
- | any ((> 0) . inCount) (M.elems is) ->
- 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
- [ "I", pc, n, a, fp, ord, obj, off ] -> do
- i <- Insn <$> unhex pc <*> unhex n <*> unhex a <*> pure fp
- <*> pure ord
- <*> pure (if obj == "-" then Nothing else Just obj)
- <*> unhex off
- 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 ds as env st
- [ "R", pc ] -> do
- r <- unhex pc
- 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 ds (BS.empty : as) env st
- [ "A", h ] -> do
- b <- unhexBytes h
- go rest is es rs ds (b : as) env st
- [ "N", n, b ] -> do
- v <- (,) <$> unhex n <*> unhex b
- 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 ds as env (Just v)
- Nothing -> Left ("not an exit status: " <> T.unpack x)
- [] -> go rest is es rs ds as env st
- _ -> Left ("an unreadable dump line: " <> T.unpack l)
+ line (d, as, env, st) l = case T.words l of
+ [ "I", pc, n, a, fp, ord, obj, off ] -> do
+ i <- Insn <$> unhex pc <*> unhex n <*> unhex a <*> pure fp
+ <*> pure ord
+ <*> pure (if obj == "-" then Nothing else Just obj)
+ <*> unhex off
+ pure (d { dpInsns = M.insert (inPc i) i (dpInsns d) }, as, env
+ , st)
+ [ "E", from, to, n ] -> do
+ f <- unhex from
+ k <- unhex to
+ c <- unhex n
+ pure (d { dpTransfers = M.insertWith M.union f (M.singleton k c)
+ (dpTransfers d) }, as, env, st)
+ [ "R", pc ] -> do
+ r <- unhex pc
+ pure (d { dpReturns = S.insert r (dpReturns d) }, as, env, st)
+ [ "D", pc, fp ] -> do
+ k <- unhex pc
+ pure (d { dpOperands = M.insert k fp (dpOperands d) }, as, env
+ , st)
+ [ "C", c, caller, call ] -> do
+ v <- (,) <$> unhex caller <*> unhex call
+ k <- unhex c
+ pure (d { dpContexts = M.insert k v (dpContexts d) }, as, env
+ , st)
+ ("K" : pc : partial : cs@(_ : _)) -> do
+ k <- unhex pc
+ p <- case partial of
+ "0" -> pure False
+ "1" -> pure True
+ _ -> Left ("an unreadable dump line: " <> T.unpack l)
+ xs <- traverse unhex cs
+ pure (d { dpCallers = M.insert k (p, xs) (dpCallers d) }, as
+ , env, st)
+ [ "T", _ ] ->
+ Left "the guest started a second thread, which a trace \
+ \cannot record: the run was stopped"
+ [ "A" ] -> pure (d, BS.empty : as, env, st)
+ [ "A", h ] -> do
+ b <- unhexBytes h
+ pure (d, b : as, env, st)
+ [ "N", n, b ] -> do
+ v <- (,) <$> unhex n <*> unhex b
+ pure (d, as, Just v, st)
+ [ "X", x ] -> case readMaybe (T.unpack x) of
+ Just v -> pure (d, as, env, Just v)
+ Nothing -> Left ("not an exit status: " <> T.unpack x)
+ [] -> pure (d, as, env, st)
+ _ -> Left ("an unreadable dump line: " <> T.unpack l)
record as env st = case (as, env, st) of
([], Nothing, Nothing) -> pure Nothing
(_ : _, Just e, Just x) -> pure (Just (Run as e x))
@@ -196,6 +228,21 @@ readDump t =
| otherwise =
BS.pack <$> traverse (fmap fromInteger . unhex) (T.chunksOf 2 h)
+-- | The calls that made a context, innermost first, at most 24 of
+-- them (as memcheck keeps): each by its object and address there,
+-- or by its run-time address where the run names no object for it.
+callsOf :: Dump -> Integer -> [(Maybe T.Text, Integer)]
+callsOf d = go (24 :: Int)
+ where
+ go n c
+ | n <= 0 || c == 0 = []
+ | otherwise = case M.lookup c (dpContexts d) of
+ Just (caller, pc) -> site pc : go (n - 1) caller
+ Nothing -> []
+ site pc = case M.lookup pc (dpInsns d) of
+ Just i | Just o <- inObject i -> (Just o, inOffset i)
+ _ -> (Nothing, pc)
+
-- | Why a run cannot be set beside the first as differing from it in
-- the secret alone, if it cannot: it ran another program, its
-- arguments differ from the first run's in number or length, or it
@@ -273,6 +320,10 @@ data Divergence = Divergence {
, dvDesigned :: !Int
-- | the offsets some run, control or not, executed, by object
, dvExecuted :: !(M.Map T.Text (S.Set Integer))
+ -- | at each origin, the distinct chains of calls that reached it
+ -- in the declared and designed runs, at most 16 of them, and
+ -- whether there were more than those
+ , dvCallers :: !(M.Map Integer ([[(Maybe T.Text, Integer)]], Bool))
} deriving (Eq, Show)
-- | Compare runs, uncontrolled.
@@ -309,8 +360,17 @@ diffDesigned cs ds xs = Divergence {
, i <- M.elems (dpInsns d)
, inCount i > 0
, Just obj <- [ inObject i ] ]
+ , dvCallers = M.fromList
+ [ (inPc i, callersAt (inPc i)) | (_, i) <- origins ]
}
where
+ callersAt pc =
+ let found = [ (partial, fmap (callsOf d) ks)
+ | d <- runs
+ , Just (partial, ks) <- [ M.lookup pc (dpCallers d) ] ]
+ stacks = L.nub (concatMap snd found)
+ in (take 16 stacks, any fst found || length stacks > 16)
+
-- what differs between the first run and a repeat of its secret
unsteady = case ds of
(d : _) -> S.unions (fmap (differing d) cs)
@@ -460,7 +520,10 @@ originText o = case o of
-- | The report: @vestigia/diff-v3@. Runs are given the declared,
-- then the designed, then the controls, and an origin names the
--- runs alike at it by the first two.
+-- runs alike at it by the first two. An origin's stacks are its own
+-- frames then its calls', innermost first, each frame with the
+-- object and address of the instruction it names, as memcheck's
+-- are in a taint report.
divergenceJson
:: T.Text -> [Named] -> M.Map (T.Text, Integer) [Place] -> Divergence
-> Value
@@ -493,12 +556,19 @@ divergenceJson version runs places dv = Object
, ("offset", String (hex (inOffset i)))
, ("count", Number (inCount i))
, ("frames", Array (fmap placeJson (placesOf i)))
+ , ("stacks", Array
+ [ Array (located (inObject i, inOffset i)
+ <> concatMap located calls)
+ | calls <- stacks ])
+ , ("partial", Bool partial)
, ("groups", Array (fmap (Array . fmap named) groups))
, ("absent", Array (fmap named absent))
]
| (o, i) <- dvOrigins dv
, let (groups, absent) = M.findWithDefault ([], []) (o, inPc i)
- (dvBehaviour dv) ])
+ (dvBehaviour dv)
+ (stacks, partial) = M.findWithDefault ([], False) (inPc i)
+ (dvCallers dv) ])
, ("downstream", Object
[ (obj, Array (fmap (String . hex) (S.toAscList offs)))
| (obj, offs) <- M.toList (M.fromListWith S.union
@@ -532,6 +602,21 @@ divergenceJson version runs places dv = Object
, ("file", maybe Null String (plFile p))
, ("line", maybe Null (Number . toInteger) (plLine p))
]
+ -- an instruction's frames, innermost first, each with where the
+ -- instruction is; one unnamed frame where nothing names it
+ located (mo, a) =
+ let at = [ ("object", maybe Null String mo)
+ , ("offset", String (hex a)) ]
+ ps = case mo of
+ Just obj -> M.findWithDefault [] (obj, a) places
+ Nothing -> []
+ in case ps of
+ [] -> [ Object (at <> [ ("function", Null), ("file", Null)
+ , ("line", Null) ]) ]
+ _ -> [ case placeJson p of
+ Object kvs -> Object (at <> kvs)
+ other -> other
+ | p <- ps ]
-- | One line per origin, innermost frame first, for a terminal.
divergenceSummary
diff --git a/nix/probe.nix b/nix/probe.nix
@@ -98,6 +98,15 @@ pkgs.runCommand "vestigia-probe-check" {
'${builtins.toJSON expected.diff}'
''}
+ # each origin's stack runs from its own function to the call in
+ # main that reached it
+ for d in ${diff} ${lib.optionalString x86_64 "${diffCross}"}; do
+ check $d/diff.json \
+ '[.origins[] | [.stacks[0][0].function, .stacks[0][1].function]
+ | .[1]] | unique' \
+ '["main"]'
+ done
+
# each run as it was made: the declared, then the control
check ${diff}/diff.json \
'[.runs[] | [.kind, .arguments[1], .status]]' \
diff --git a/plugin/vestigia-qemu.c b/plugin/vestigia-qemu.c
@@ -18,13 +18,18 @@
* Nothing needs aligning, and no taint is propagated, so effects of
* 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
+ * It reads each instruction's bytes, x86_64's or aarch64's, for three
* 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.
+ * but on other operands computed them from the secret. And a call,
+ * with the returns, keeps a shadow stack of the calls in progress,
+ * so that an instruction that could be an origin (one ending a
+ * translation block, as every branch does, one touching memory, or a
+ * division) is given the contexts it ran in: the chains of calls, by
+ * their addresses, that reached it, up to CONTEXTS of them.
*
* At exit it writes, to the file named by its `out` argument:
*
@@ -32,6 +37,8 @@
* E <from> <to> <count>
* R <pc>
* D <pc> <operands>
+ * C <context> <caller> <call>
+ * K <pc> <partial> <context>...
*
* in hex, where <object> is the file the instruction's bytes were
* mapped from ("-" if none, or if the file's program headers cannot
@@ -39,7 +46,10 @@
* 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. A
- * guest that started a second thread gets the line `T 2` alone.
+ * context is the call at <call> made in context <caller>, context 0
+ * being the program's own; <partial> is 1 where an instruction ran in
+ * more contexts than are kept. 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
@@ -58,7 +68,10 @@
QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
/* what an instruction is to a comparison, read from its bytes */
-enum { PLAIN, RETURN, DIVISION };
+enum { PLAIN, RETURN, DIVISION, CALL };
+
+/* the most contexts kept for one instruction */
+#define CONTEXTS 16
/* 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 */
@@ -83,13 +96,35 @@ typedef struct Insn {
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 */
+ uint32_t last; /* the context it last ran in */
+ uint32_t contexts[CONTEXTS];
+ int ncontexts, partial;
+ int origin; /* it ends a block or divides: it could be one */
+ /* a call's: the context it was last made in, and the one it made */
+ uint32_t made_in, made;
} Insn;
+/* a context: the context a call was made in, and the call */
+typedef struct Context {
+ uint32_t caller;
+ uint64_t call;
+} Context;
+
+/* a call in progress: where it returns, and the context it left */
+typedef struct Call {
+ uint64_t ret;
+ uint32_t left;
+} Call;
+
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 GArray *contexts; /* Context by number, 0 the program's own */
+static GHashTable *interned; /* Context -> its number */
+static GArray *calls; /* the calls in progress, innermost last */
+static uint32_t current; /* the context the guest runs in */
static struct qemu_plugin_register *gpr[GPRS];
static GByteArray *regbuf;
@@ -106,6 +141,12 @@ static Decoded decode_aarch64(const uint8_t *b, size_t n) {
if ((w & 0xfffffc1f) == 0xd65f0000 || w == 0xd65f0bff
|| w == 0xd65f0fff)
d.kind = RETURN;
+ /* BL, BLR, BLRAAZ, BLRABZ, BLRAA, BLRAB */
+ else if ((w & 0xfc000000) == 0x94000000
+ || (w & 0xfffffc1f) == 0xd63f0000
+ || (w & 0xfffff81f) == 0xd63f081f
+ || (w & 0xfffff800) == 0xd73f0800)
+ d.kind = CALL;
/* UDIV, SDIV */
else if ((w & 0x7fe0f800) == 0x1ac00800) {
d.kind = DIVISION;
@@ -132,6 +173,10 @@ static Decoded decode_x86_64(const uint8_t *b, size_t n) {
if (k >= n) return d;
/* RET, RET imm16 */
if (b[k] == 0xc3 || b[k] == 0xc2) d.kind = RETURN;
+ /* CALL rel32, CALL r/m: FF with ModRM's reg 2 */
+ else if (b[k] == 0xe8
+ || (b[k] == 0xff && k + 1 < n && ((b[k + 1] >> 3) & 7) == 2))
+ d.kind = CALL;
/* 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) {
@@ -161,6 +206,8 @@ static Insn *insn_at(uint64_t pc, uint64_t size, uintptr_t haddr,
i->fingerprint = fnv_offset;
i->order = fnv_offset;
i->operands = fnv_offset;
+ i->last = UINT32_MAX;
+ i->made_in = UINT32_MAX;
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);
@@ -179,15 +226,77 @@ static void transfer(Insn *from, uint64_t to) {
(*n)++;
}
+static guint context_hash(gconstpointer p) {
+ const Context *c = p;
+ return (guint)((c->call * 0x9e3779b97f4a7c15ULL) >> 32) ^ c->caller;
+}
+
+static gboolean context_equal(gconstpointer a, gconstpointer b) {
+ const Context *x = a, *y = b;
+ return x->caller == y->caller && x->call == y->call;
+}
+
+static uint32_t context_of(uint32_t caller, uint64_t call) {
+ Context c = { caller, call };
+ gpointer v;
+ if (g_hash_table_lookup_extended(interned, &c, NULL, &v))
+ return GPOINTER_TO_UINT(v);
+ uint32_t n = contexts->len;
+ g_array_append_val(contexts, c);
+ g_hash_table_insert(interned, g_memdup2(&c, sizeof c),
+ GUINT_TO_POINTER(n));
+ return n;
+}
+
+/* a call made: it returns past itself */
+static void enter(Insn *call) {
+ Call c = { call->pc + call->size, current };
+ g_array_append_val(calls, c);
+ if (call->made_in != current) {
+ call->made_in = current;
+ call->made = context_of(current, call->pc);
+ }
+ current = call->made;
+}
+
+/* a return made, to pc: the innermost call returning there ends, and
+ any inside it that never returned; a return no call made leaves
+ the stack as it is */
+static void leave(uint64_t pc) {
+ for (guint k = calls->len; k > 0; k--) {
+ const Call *c = &g_array_index(calls, Call, k - 1);
+ if (c->ret == pc) {
+ current = c->left;
+ g_array_set_size(calls, k - 1);
+ return;
+ }
+ }
+}
+
+static void note_context(Insn *i) {
+ i->last = current;
+ /* once more have been seen than are kept, no more is learnt */
+ if (i->partial) return;
+ for (int k = 0; k < i->ncontexts; k++)
+ if (i->contexts[k] == current) return;
+ if (i->ncontexts < CONTEXTS)
+ i->contexts[i->ncontexts++] = current;
+ else
+ i->partial = 1;
+}
+
static void on_exec(unsigned int vcpu, void *udata) {
Insn *i = udata;
(void)vcpu;
if (prev != NULL) {
prev->order = (prev->order ^ i->pc) * fnv_prime;
if (i->pc != prev->pc + prev->size) transfer(prev, i->pc);
+ if (prev->d.kind == CALL) enter(prev);
+ else if (prev->d.kind == RETURN) leave(i->pc);
}
prev = i;
i->count++;
+ if (i->origin && i->last != current) note_context(i);
}
static void mix(Insn *i, uint64_t v) {
@@ -231,6 +340,7 @@ static void on_mem(unsigned int vcpu, qemu_plugin_meminfo_t info,
(void)vcpu;
i->fingerprint = (i->fingerprint ^ vaddr) * fnv_prime;
i->accesses++;
+ if (i->last != current) note_context(i);
if (i->d.kind == DIVISION) {
qemu_plugin_mem_value v = qemu_plugin_mem_get_value(info);
switch (v.type) {
@@ -302,6 +412,7 @@ static void on_translate(qemu_plugin_id_t id, struct qemu_plugin_tb *tb) {
(uintptr_t)qemu_plugin_insn_haddr(qi),
aarch64 ? decode_aarch64(bytes, len)
: decode_x86_64(bytes, len));
+ if (k == n - 1 || i->d.kind == DIVISION) i->origin = 1;
qemu_plugin_register_vcpu_insn_exec_cb(qi, on_exec,
QEMU_PLUGIN_CB_NO_REGS, i);
if (i->d.kind == DIVISION)
@@ -447,6 +558,12 @@ static void at_exit(qemu_plugin_id_t id, void *p) {
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);
+ if (i->ncontexts > 0) {
+ fprintf(out, "K %" PRIx64 " %d", i->pc, i->partial);
+ for (int k = 0; k < i->ncontexts; k++)
+ fprintf(out, " %" PRIx32, i->contexts[k]);
+ fprintf(out, "\n");
+ }
GHashTableIter jt;
gpointer tk, tn;
g_hash_table_iter_init(&jt, i->succ);
@@ -454,6 +571,11 @@ static void at_exit(qemu_plugin_id_t id, void *p) {
fprintf(out, "E %" PRIx64 " %" PRIx64 " %" PRIx64 "\n", i->pc,
*(uint64_t *)tk, *(uint64_t *)tn);
}
+ for (guint k = 1; k < contexts->len; k++) {
+ const Context *c = &g_array_index(contexts, Context, k);
+ fprintf(out, "C %x %" PRIx32 " %" PRIx64 "\n", k, c->caller,
+ c->call);
+ }
fclose(out);
}
@@ -470,6 +592,14 @@ QEMU_PLUGIN_EXPORT int qemu_plugin_install(qemu_plugin_id_t id,
}
insns = g_hash_table_new(g_int64_hash, g_int64_equal);
regbuf = g_byte_array_new();
+ contexts = g_array_new(FALSE, FALSE, sizeof(Context));
+ interned = g_hash_table_new_full(context_hash, context_equal, g_free,
+ NULL);
+ calls = g_array_new(FALSE, FALSE, sizeof(Call));
+ {
+ Context own = { 0, 0 };
+ g_array_append_val(contexts, own);
+ }
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
@@ -299,6 +299,30 @@ diffTests = testGroup "diff"
-- a control dividing other operands sets it apart as unsteady
fmap inPc (dvUnsteady (diffControlled [ x ] [ a, b ])) @?= [ 0x40 ]
+ , testCase "an origin is given the calls that reached it" $ do
+ -- 0x10 ran in context 2 (the call at 0x40 made in context 1,
+ -- the call at 0x30 made in the program's own) in A, and in the
+ -- program's own context too in B
+ let calls = T.unlines
+ [ "C 1 0 30", "C 2 1 40" ]
+ a <- either assertFailure pure (readDump (dumpA <> calls
+ <> "K 10 0 2\n"))
+ b <- either assertFailure pure (readDump (dumpB <> calls
+ <> "K 10 1 2 0\n"))
+ callsOf a 2 @?= [ (Just "/lib.so", 0x40), (Just "/lib.so", 0x30) ]
+ callsOf a 0 @?= []
+ M.lookup 0x10 (dvCallers (diffDumps [ a, b ]))
+ @?= Just ([ [ (Just "/lib.so", 0x40), (Just "/lib.so", 0x30) ]
+ , [] ], True)
+ M.lookup 0x10 (dvCallers (diffDumps [ a, a ]))
+ @?= Nothing
+
+ , testCase "contexts that do not chain back are refused" $ do
+ isLeft (readDump (dumpA <> "C 1 2 30\nC 2 1 40\n"))
+ @? "a context made in a later one"
+ isLeft (readDump (dumpA <> "K 10 0 5\n"))
+ @? "a context never made"
+
, testCase "identical runs have no origins" $ do
a <- either assertFailure pure (readDump dumpA)
let dv = diffDumps [ a, a ]
diff --git a/vestigia.cabal b/vestigia.cabal
@@ -56,6 +56,7 @@ executable vestigia
build-depends:
base
, bytestring
+ , containers
, directory
, filepath
, process
