Skip to content

armgit / rea

Public Imported from GitHub
0

Reverse engineer anything with agents, from app behavior down to native binaries.

24.5 KB
Raw Blame
import canonicalize from "canonicalize";

import { digestCanonicalValue } from "../canonicalDigest.js";
import type { ManagedMemberInspection } from "./managedArtifact.js";
import type { ManagedMemberComparisonResult } from "./managedMemberComparison.js";
import type {
  ManagedFieldMatches,
  ManagedMethodMatches,
} from "./managedMemberComparisonMatch.js";
import { signatureIdentity } from "./managedMemberSignatureIdentity.js";
import { isManagedMemberReferenceInstruction } from "./managedMemberInstructionFacts.js";

type Method = ManagedMemberInspection["methods"][number];
type Field = ManagedMemberInspection["fields"][number];
type CallEdgesByCaller = ReadonlyMap<
  string,
  readonly ManagedMemberInspection["call_edges"][number][]
>;
type MethodItem = ManagedMemberComparisonResult["methods"][number];
type FieldItem = ManagedMemberComparisonResult["fields"][number];
type UnmatchedComparison = Extract<
  MethodItem["match"],
  { readonly status: "unmatched" }
>;

type OneSided<Item> =
  | { readonly left: Item; readonly right?: never }
  | { readonly left?: never; readonly right: Item };

interface ComparisonItemContext {
  readonly leftEvidenceId: string;
  readonly rightEvidenceId: string;
  readonly leftComplete: boolean;
  readonly rightComplete: boolean;
  /** Declaring types each side selected; null when it inspected every type. */
  readonly leftSelection: ReadonlySet<string> | null;
  readonly rightSelection: ReadonlySet<string> | null;
  /** Whether matching keyed signatures by resolved digests, not raw bytes. */
  readonly signatureResolutionExamined: boolean;
  readonly leftCallEdgesByCaller: CallEdgesByCaller;
  readonly rightCallEdgesByCaller: CallEdgesByCaller;
}

/** Whether an inventory observed every member of this member's declaring type. */
const inventoryCovers = (
  complete: boolean,
  selection: ReadonlySet<string> | null,
  member: Method | Field,
): boolean =>
  complete &&
  (selection === null ||
    (member.declaring_type !== null && selection.has(member.declaring_type)));

/**
 * Declared type and name of each unpaired member, per side, whose signature
 * was not decoded, or was decoded but not resolved while matching keyed
 * resolved signatures.
 */
interface UndecodedOneSidedNames {
  readonly resolved: boolean;
  readonly undecoded: Readonly<Record<"left" | "right", ReadonlySet<string>>>;
  readonly unresolved: Readonly<Record<"left" | "right", ReadonlySet<string>>>;
  readonly unknownOwners: Readonly<
    Record<"left" | "right", ReadonlySet<string>>
  >;
}

const methodDimensions = (
  left: Method,
  right: Method,
  leftCallEdgesByCaller: CallEdgesByCaller,
  rightCallEdgesByCaller: CallEdgesByCaller,
): {
  readonly dimensions: MethodItem["dimensions"];
  readonly bodyUnknown: boolean;
  readonly callTargetUnknown: boolean;
} => {
  const dimensions: MethodItem["dimensions"] = [];
  const headerFields = ["max_stack", "init_locals"] as const;
  const headerChanged = headerFields.some(
    (field) =>
      left.body[field] !== null &&
      right.body[field] !== null &&
      left.body[field] !== right.body[field],
  );
  const localsPresenceChanged =
    left.body.status === "present" &&
    right.body.status === "present" &&
    (left.body.local_var_sig_token !== null) !==
      (right.body.local_var_sig_token !== null);
  if (
    left.flags !== right.flags ||
    left.impl_flags !== right.impl_flags ||
    headerChanged ||
    localsPresenceChanged
  )
    dimensions.push("metadata");
  if (signatureIdentity(left.signature) !== signatureIdentity(right.signature))
    dimensions.push("signature");
  const leftBodyComplete =
    left.body.status === "present" && left.body.truncated_instructions === 0;
  const rightBodyComplete =
    right.body.status === "present" && right.body.truncated_instructions === 0;
  const bothAbsent =
    left.body.status === "absent" && right.body.status === "absent";
  if (
    (left.body.status === "absent" && rightBodyComplete) ||
    (right.body.status === "absent" && leftBodyComplete)
  )
    dimensions.push("availability");
  if (bothAbsent)
    return { dimensions, bodyUnknown: false, callTargetUnknown: false };
  const sameCallShape =
    callShape(left.body.anchors) === callShape(right.body.anchors);
  const callTargets = sameCallShape
    ? compareCallTargets(
        left,
        right,
        leftCallEdgesByCaller.get(left.token) ?? [],
        rightCallEdgesByCaller.get(right.token) ?? [],
      )
    : { changed: false, unknown: false };
  if (callTargets.changed) dimensions.push("call-target");
  if (!leftBodyComplete || !rightBodyComplete)
    return {
      dimensions,
      bodyUnknown: true,
      callTargetUnknown: callTargets.unknown,
    };
  if (!sameCallShape) dimensions.push("call-shape");
  // The decoded fingerprint omits switch targets and is not exact CIL identity.
  if (
    left.body.il_sha256 !== right.body.il_sha256 ||
    left.body.normalized_il_sha256 !== right.body.normalized_il_sha256
  )
    dimensions.push("cil");
  if (
    canonicalize(left.body.opcode_counts) !==
    canonicalize(right.body.opcode_counts)
  )
    dimensions.push("opcode-shape");
  if (fieldShape(left.body.anchors) !== fieldShape(right.body.anchors))
    dimensions.push("field-shape");
  if (
    canonicalize(left.body.exception_regions) !==
    canonicalize(right.body.exception_regions)
  )
    dimensions.push("exception-shape");
  return {
    dimensions,
    callTargetUnknown: callTargets.unknown,
    bodyUnknown: headerFields.some(
      (field) => left.body[field] === null || right.body[field] === null,
    ),
  };
};

const compareCallTargets = (
  left: Method,
  right: Method,
  leftEdges: readonly ManagedMemberInspection["call_edges"][number][],
  rightEdges: readonly ManagedMemberInspection["call_edges"][number][],
): { readonly changed: boolean; readonly unknown: boolean } => {
  const callAnchors = (method: Method) =>
    method.body.anchors.filter(
      (instruction) =>
        isManagedMemberReferenceInstruction(instruction) &&
        instruction.operand_kind === "method",
    );
  const leftAnchors = callAnchors(left);
  const rightAnchors = callAnchors(right);
  if (leftAnchors.length !== rightAnchors.length)
    return { changed: false, unknown: true };
  if (
    leftEdges.length !== leftAnchors.length ||
    rightEdges.length !== rightAnchors.length ||
    leftEdges.some(
      (edge, index) => edge.opcode !== leftAnchors[index]?.opcode,
    ) ||
    rightEdges.some(
      (edge, index) => edge.opcode !== rightAnchors[index]?.opcode,
    )
  )
    return { changed: false, unknown: true };

  let changed = false;
  let unknown = false;
  for (let index = 0; index < leftEdges.length; index++) {
    const leftEdge = leftEdges[index];
    const rightEdge = rightEdges[index];
    if (leftEdge === undefined || rightEdge === undefined) {
      unknown = true;
      continue;
    }
    for (const field of ["target_name", "target_declaring_type"] as const) {
      const leftValue = leftEdge[field];
      const rightValue = rightEdge[field];
      if (leftValue === null || rightValue === null) unknown = true;
      else if (leftValue !== rightValue) changed = true;
    }
  }
  return { changed, unknown };
};

const callShape = (anchors: Method["body"]["anchors"]): string =>
  JSON.stringify(
    anchors
      .filter(
        (instruction) =>
          isManagedMemberReferenceInstruction(instruction) &&
          instruction.operand_kind === "method",
      )
      .map(({ opcode, operand_kind }) => [opcode, operand_kind]),
  );

const fieldShape = (anchors: Method["body"]["anchors"]): string =>
  JSON.stringify(
    anchors
      .filter(
        (instruction) =>
          isManagedMemberReferenceInstruction(instruction) &&
          instruction.operand_kind === "field",
      )
      .map(({ opcode, operand_kind }) => [opcode, operand_kind]),
  );

const methodIdentity = (item: Method): NonNullable<MethodItem["left"]> => ({
  token: item.token,
  declaring_type: item.declaring_type,
  name: item.name,
  signature_sha256: item.signature.raw_sha256,
  normalized_il_sha256: item.body.normalized_il_sha256,
});

const fieldIdentity = (item: Field): NonNullable<FieldItem["left"]> => ({
  token: item.token,
  declaring_type: item.declaring_type,
  name: item.name,
  signature_sha256: item.signature.raw_sha256,
});

const unmatchedComparison = (): UnmatchedComparison => ({
  status: "unmatched",
  basis: "none",
  confidence: "unknown",
  candidate_left_tokens: [],
  candidate_right_tokens: [],
});

const methodOnlyItem = (
  member: OneSided<Method>,
  identity: string,
  identityUnavailable: boolean,
  context: ComparisonItemContext,
  undecoded: UndecodedOneSidedNames,
): MethodItem => {
  if (member.left !== undefined) {
    const limitations = absenceLimitations(member.left, identity, {
      oppositeComplete: inventoryCovers(
        context.rightComplete,
        context.rightSelection,
        member.left,
      ),
      unpaired: undecoded,
      ownIdentityUnavailable: identityUnavailable,
      opposite: "right",
      inventory: "method",
    });
    return {
      item_id: `mmc_method_${digestCanonicalValue({ token: member.left.token, side: "left" }, "Managed comparison")}`,
      status: limitations.length === 0 ? "removed" : "unknown",
      left: methodIdentity(member.left),
      right: null,
      match: unmatchedComparison(),
      dimensions: ["availability"],
      evidence_links: [context.leftEvidenceId, context.rightEvidenceId],
      limitations,
    };
  }

  const limitations = absenceLimitations(member.right, identity, {
    oppositeComplete: inventoryCovers(
      context.leftComplete,
      context.leftSelection,
      member.right,
    ),
    unpaired: undecoded,
    ownIdentityUnavailable: identityUnavailable,
    opposite: "left",
    inventory: "method",
  });
  return {
    item_id: `mmc_method_${digestCanonicalValue({ token: member.right.token, side: "right" }, "Managed comparison")}`,
    status: limitations.length === 0 ? "added" : "unknown",
    left: null,
    right: methodIdentity(member.right),
    match: unmatchedComparison(),
    dimensions: ["availability"],
    evidence_links: [context.leftEvidenceId, context.rightEvidenceId],
    limitations,
  };
};

/**
 * Why a one-sided member's absence from the other inventory was not
 * observed: that inventory is incomplete, the member's own signature was not
 * decoded, so no shape round could seek a changed counterpart, or the other
 * inventory has an unpaired (one-sided or ambiguous) same-named member whose
 * signature was not decoded, which may be this member with a changed
 * signature. A decoded signature that names a type REA could not name, while
 * the comparison otherwise keys resolved signatures, is compared by raw bytes
 * that name types by build-local row, so it is treated the same way.
 */
const absenceLimitations = (
  member: Method | Field,
  identity: string,
  opposite: {
    readonly oppositeComplete: boolean;
    readonly ownIdentityUnavailable: boolean;
    readonly unpaired: UndecodedOneSidedNames;
    readonly opposite: "left" | "right";
    readonly inventory: "method" | "field";
  },
): string[] => [
  ...(opposite.ownIdentityUnavailable
    ? [
        "declaring-type-name-not-resolved: Declared type identity could not be resolved; a bare display name cannot establish a counterpart or absence.",
      ]
    : []),
  ...(opposite.unpaired.unknownOwners[opposite.opposite].has(member.name)
    ? [
        `counterpart-declaring-type-name-not-resolved: The ${opposite.opposite} ${opposite.inventory} inventory has an unpaired same-named member with unresolved enclosing-name identity, so absence was not established.`,
      ]
    : []),
  ...(opposite.oppositeComplete
    ? []
    : [
        `unknown-within-incomplete-metadata: The ${opposite.opposite} ${opposite.inventory} inventory is incomplete, so absence was not observed.`,
      ]),
  ...(member.signature.parse_status === "decoded"
    ? []
    : [
        `signature-not-decoded: The member's ${member.signature.parse_status} signature was compared only by exact declared type, name, and signature bytes, so a changed or renamed counterpart could not be sought.`,
      ]),
  ...(member.signature.parse_status === "decoded" &&
  opposite.unpaired.undecoded[opposite.opposite].has(identity)
    ? [
        `counterpart-signature-not-decoded: The ${opposite.opposite} ${opposite.inventory} inventory has an unpaired member with the same declared type and name whose signature was not decoded, so it may be this member with a changed signature.`,
      ]
    : []),
  ...(unresolved(member, opposite.unpaired.resolved)
    ? [
        `signature-not-resolved: The member's signature names a type REA could not name, so it was compared by raw bytes, which name types by build-local metadata row; a counterpart whose referenced type moved rows could not be found.`,
      ]
    : []),
  ...(member.signature.parse_status === "decoded" &&
  !unresolved(member, opposite.unpaired.resolved) &&
  opposite.unpaired.unresolved[opposite.opposite].has(identity)
    ? [
        `counterpart-signature-not-resolved: The ${opposite.opposite} ${opposite.inventory} inventory has an unpaired member with the same declared type and name whose signature names a type REA could not name, so it may be this member.`,
      ]
    : []),
];

/** A known signature form whose type operands still compare by raw bytes. */
const unresolved = (member: Method | Field, resolved: boolean): boolean =>
  resolved &&
  member.signature.kind !== "unknown" &&
  member.signature.resolved_sha256 === null;

/** Equal build-local bytes cannot establish equal unresolved type operands. */
const pairedSignatureLimitations = (
  left: Method | Field,
  right: Method | Field,
  examined: boolean,
): string[] =>
  unresolved(left, examined) || unresolved(right, examined)
    ? [
        "signature-not-resolved: At least one signature names a type REA could not resolve; equal build-local row bytes do not establish equivalent signature types.",
      ]
    : [];

/**
 * Declared names of unpaired members whose signature was not decoded: one-sided
 * members and candidates of ambiguous groups, which also remain unpaired.
 */
interface Unpaired {
  readonly item: Method | Field;
  readonly identity: string;
  readonly identityUnavailable: boolean;
}

const undecodedOneSidedNames = (
  members: {
    readonly leftOnly: readonly Unpaired[];
    readonly rightOnly: readonly Unpaired[];
    readonly ambiguous: readonly {
      readonly left: readonly Unpaired[];
      readonly right: readonly Unpaired[];
    }[];
  },
  resolved: boolean,
): UndecodedOneSidedNames => {
  const sides = {
    left: [
      ...members.leftOnly,
      ...members.ambiguous.flatMap(({ left }) => left),
    ],
    right: [
      ...members.rightOnly,
      ...members.ambiguous.flatMap(({ right }) => right),
    ],
  };
  const names = (
    side: readonly Unpaired[],
    keep: (item: Method | Field) => boolean,
  ) =>
    new Set(
      side.filter(({ item }) => keep(item)).map(({ identity }) => identity),
    );
  const undecoded = (item: Method | Field) =>
    item.signature.parse_status !== "decoded";
  const notResolved = (item: Method | Field) => unresolved(item, resolved);
  return {
    resolved,
    unknownOwners: {
      left: new Set(
        sides.left.filter((x) => x.identityUnavailable).map((x) => x.item.name),
      ),
      right: new Set(
        sides.right
          .filter((x) => x.identityUnavailable)
          .map((x) => x.item.name),
      ),
    },
    undecoded: {
      left: names(sides.left, undecoded),
      right: names(sides.right, undecoded),
    },
    unresolved: {
      left: names(sides.left, notResolved),
      right: names(sides.right, notResolved),
    },
  };
};

const fieldOnlyItem = (
  member: OneSided<Field>,
  identity: string,
  identityUnavailable: boolean,
  context: ComparisonItemContext,
  undecoded: UndecodedOneSidedNames,
): FieldItem => {
  if (member.left !== undefined) {
    const limitations = absenceLimitations(member.left, identity, {
      oppositeComplete: inventoryCovers(
        context.rightComplete,
        context.rightSelection,
        member.left,
      ),
      unpaired: undecoded,
      ownIdentityUnavailable: identityUnavailable,
      opposite: "right",
      inventory: "field",
    });
    return {
      item_id: `mmc_field_${digestCanonicalValue({ token: member.left.token, side: "left" }, "Managed comparison")}`,
      status: limitations.length === 0 ? "removed" : "unknown",
      left: fieldIdentity(member.left),
      right: null,
      match: unmatchedComparison(),
      evidence_links: [context.leftEvidenceId, context.rightEvidenceId],
      limitations,
    };
  }

  const limitations = absenceLimitations(member.right, identity, {
    oppositeComplete: inventoryCovers(
      context.leftComplete,
      context.leftSelection,
      member.right,
    ),
    unpaired: undecoded,
    ownIdentityUnavailable: identityUnavailable,
    opposite: "left",
    inventory: "field",
  });
  return {
    item_id: `mmc_field_${digestCanonicalValue({ token: member.right.token, side: "right" }, "Managed comparison")}`,
    status: limitations.length === 0 ? "added" : "unknown",
    left: null,
    right: fieldIdentity(member.right),
    match: unmatchedComparison(),
    evidence_links: [context.leftEvidenceId, context.rightEvidenceId],
    limitations,
  };
};

/**
 * Name only evidence shared by the whole group. Exact-signature ambiguities
 * include both declared-identity collisions and unresolved signature choices.
 */
const ambiguityLimitation = (
  members: "methods" | "fields",
  basis: MethodItem["match"]["basis"],
  identityUnavailable: boolean,
): string =>
  identityUnavailable
    ? "declaring-type-name-not-resolved: Declared type identity remains unresolved; REA did not guess a counterpart from display names, signatures or CIL."
    : basis === "exact-signature"
      ? `Multiple managed ${members} share the same signature; REA did not guess declared ownership or a token remap.`
      : basis === "exact-il-signature"
        ? "Multiple managed methods share the same CIL and signature; REA did not guess a token remap."
        : members === "methods"
          ? "Multiple managed methods share the same structural shape; REA did not guess a token remap."
          : "Multiple managed fields share the same signature; REA did not guess a token remap.";

export const buildMethodItems = (
  matches: ManagedMethodMatches,
  context: ComparisonItemContext,
): MethodItem[] => {
  const items: MethodItem[] = [];
  for (const pair of matches.pairs) {
    const signatureLimitations = pairedSignatureLimitations(
      pair.left.item,
      pair.right.item,
      context.signatureResolutionExamined,
    );
    const {
      dimensions: observedDimensions,
      bodyUnknown,
      callTargetUnknown,
    } = methodDimensions(
      pair.left.item,
      pair.right.item,
      context.leftCallEdgesByCaller,
      context.rightCallEdgesByCaller,
    );
    const dimensions = [
      ...observedDimensions,
      ...(bodyUnknown ? (["body-coverage"] as const) : []),
      ...(callTargetUnknown ? (["availability"] as const) : []),
    ];
    const observedChange = observedDimensions.length > 0;
    items.push({
      item_id: `mmc_method_${digestCanonicalValue(
        {
          left: pair.left.item.token,
          right: pair.right.item.token,
          basis: pair.basis,
        },
        "Managed comparison",
      )}`,
      status: observedChange
        ? "changed"
        : bodyUnknown || callTargetUnknown || signatureLimitations.length > 0
          ? "unknown"
          : "unchanged",
      left: methodIdentity(pair.left.item),
      right: methodIdentity(pair.right.item),
      match: {
        status: "matched",
        basis: pair.basis,
        confidence: pair.confidence,
        candidate_left_tokens: [],
        candidate_right_tokens: [],
      },
      dimensions,
      evidence_links: [context.leftEvidenceId, context.rightEvidenceId],
      limitations: [
        ...signatureLimitations,
        ...(bodyUnknown
          ? [
              "Method body facets are unknown because at least one side has unavailable or partial body data.",
            ]
          : []),
        ...(callTargetUnknown
          ? [
              "One or more call targets are unavailable because the observed method edges do not cover aligned call instructions or lack a target name or declaring type.",
            ]
          : []),
      ],
    });
  }
  for (const ambiguous of matches.ambiguous) {
    items.push({
      item_id: `mmc_method_${digestCanonicalValue(
        {
          left: ambiguous.left.map(({ item }) => item.token),
          right: ambiguous.right.map(({ item }) => item.token),
          basis: ambiguous.basis,
        },
        "Managed comparison",
      )}`,
      status: "unknown",
      left: null,
      right: null,
      match: {
        status: "ambiguous",
        basis: ambiguous.basis,
        confidence: "unknown",
        candidate_left_tokens: ambiguous.left.map(({ item }) => item.token),
        candidate_right_tokens: ambiguous.right.map(({ item }) => item.token),
      },
      dimensions: ["availability"],
      evidence_links: [context.leftEvidenceId, context.rightEvidenceId],
      limitations: [
        ambiguityLimitation(
          "methods",
          ambiguous.basis,
          ambiguous.left.some((item) => item.identityUnavailable) ||
            ambiguous.right.some((item) => item.identityUnavailable),
        ),
      ],
    });
  }
  const undecoded = undecodedOneSidedNames(
    matches,
    context.signatureResolutionExamined,
  );
  for (const item of matches.leftOnly)
    items.push(
      methodOnlyItem(
        { left: item.item },
        item.identity,
        item.identityUnavailable,
        context,
        undecoded,
      ),
    );
  for (const item of matches.rightOnly)
    items.push(
      methodOnlyItem(
        { right: item.item },
        item.identity,
        item.identityUnavailable,
        context,
        undecoded,
      ),
    );
  return items;
};

export const buildFieldItems = (
  matches: ManagedFieldMatches,
  context: ComparisonItemContext,
): FieldItem[] => {
  const items: FieldItem[] = [];
  for (const pair of matches.pairs) {
    const signatureLimitations = pairedSignatureLimitations(
      pair.left.item,
      pair.right.item,
      context.signatureResolutionExamined,
    );
    const changed =
      signatureIdentity(pair.left.item.signature) !==
        signatureIdentity(pair.right.item.signature) ||
      pair.left.item.flags !== pair.right.item.flags;
    items.push({
      item_id: `mmc_field_${digestCanonicalValue(
        {
          left: pair.left.item.token,
          right: pair.right.item.token,
        },
        "Managed comparison",
      )}`,
      status: changed
        ? "changed"
        : signatureLimitations.length > 0
          ? "unknown"
          : "unchanged",
      left: fieldIdentity(pair.left.item),
      right: fieldIdentity(pair.right.item),
      match: {
        status: "matched",
        basis: pair.basis,
        confidence: pair.confidence,
        candidate_left_tokens: [],
        candidate_right_tokens: [],
      },
      evidence_links: [context.leftEvidenceId, context.rightEvidenceId],
      limitations: signatureLimitations,
    });
  }
  for (const ambiguous of matches.ambiguous)
    items.push({
      item_id: `mmc_field_${digestCanonicalValue(
        {
          left: ambiguous.left.map(({ item }) => item.token),
          right: ambiguous.right.map(({ item }) => item.token),
        },
        "Managed comparison",
      )}`,
      status: "unknown",
      left: null,
      right: null,
      match: {
        status: "ambiguous",
        basis: ambiguous.basis,
        confidence: "unknown",
        candidate_left_tokens: ambiguous.left.map(({ item }) => item.token),
        candidate_right_tokens: ambiguous.right.map(({ item }) => item.token),
      },
      evidence_links: [context.leftEvidenceId, context.rightEvidenceId],
      limitations: [
        ambiguityLimitation(
          "fields",
          ambiguous.basis,
          ambiguous.left.some((item) => item.identityUnavailable) ||
            ambiguous.right.some((item) => item.identityUnavailable),
        ),
      ],
    });
  const undecoded = undecodedOneSidedNames(
    matches,
    context.signatureResolutionExamined,
  );
  for (const item of matches.leftOnly)
    items.push(
      fieldOnlyItem(
        { left: item.item },
        item.identity,
        item.identityUnavailable,
        context,
        undecoded,
      ),
    );
  for (const item of matches.rightOnly)
    items.push(
      fieldOnlyItem(
        { right: item.item },
        item.identity,
        item.identityUnavailable,
        context,
        undecoded,
      ),
    );
  return items;
};