use rf_classify::{Classification, TerminatorClass};
#[derive(Debug)]
pub struct SeqPattern {
pieces: Vec<regex::Regex>,
}
impl SeqPattern {
pub fn parse(pattern: &str) -> Result<SeqPattern, String> {
let mut pieces = Vec::new();
for raw in pattern.split(';') {
let piece = raw.trim();
if piece.is_empty() {
continue;
}
let re = regex::Regex::new(&format!("(?i)^{}$", translate(piece)))
.map_err(|e| format!("invalid --search pattern {pattern:?}: {e}"))?;
pieces.push(re);
}
if pieces.is_empty() {
return Err(format!(
"--search pattern {pattern:?} is empty; expected e.g. 'pop rdi; ret'"
));
}
Ok(SeqPattern { pieces })
}
pub fn matches(&self, insns: &[&str]) -> bool {
if self.pieces.len() > insns.len() {
return false;
}
(0..=insns.len() - self.pieces.len()).any(|start| {
self.pieces
.iter()
.zip(&insns[start..])
.all(|(re, ins)| re.is_match(ins.trim()))
})
}
}
fn translate(piece: &str) -> String {
let mut out = String::with_capacity(piece.len() * 2);
let mut chars = piece.chars().peekable();
while let Some(c) = chars.next() {
match c {
'?' => out.push('.'),
'%' => out.push_str(".*"),
c if c.is_whitespace() => {
while chars.peek().is_some_and(|n| n.is_whitespace()) {
chars.next();
}
out.push_str(r"\s+");
}
c => out.push_str(®ex::escape(c.encode_utf8(&mut [0u8; 4]))),
}
}
out
}
pub fn norm_reg(r: &str) -> String {
let t = r.trim();
let t = t
.strip_prefix('$')
.or_else(|| t.strip_prefix('%'))
.unwrap_or(t);
t.to_ascii_lowercase()
}
pub const LIST_SEPARATORS: [char; 2] = [',', '|'];
fn split_list(v: Option<&str>) -> Vec<String> {
v.map(|s| {
s.split(LIST_SEPARATORS)
.map(norm_reg)
.filter(|x| !x.is_empty())
.collect()
})
.unwrap_or_default()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum TermQuery {
Kind(&'static str),
Class(TerminatorClass),
Any,
}
impl TermQuery {
const KINDS: &'static [&'static str] = &["ret", "jmp", "call", "syscall", "none"];
fn parse(s: &str) -> Option<TermQuery> {
if s == "any" {
return Some(TermQuery::Any);
}
if let Some(k) = Self::KINDS.iter().find(|k| **k == s) {
return Some(TermQuery::Kind(k));
}
if s == "bare-ret" {
return Some(TermQuery::Class(TerminatorClass::Ret));
}
TerminatorClass::parse(s).map(TermQuery::Class)
}
fn matches(self, c: &Classification) -> bool {
match self {
TermQuery::Any => true,
TermQuery::Kind(k) => c.terminator().kind() == k,
TermQuery::Class(t) => c.terminator_class() == t,
}
}
fn vocabulary() -> String {
let mut v: Vec<&str> = Self::KINDS.to_vec();
v.push("any");
v.push("bare-ret");
for t in TerminatorClass::ALL {
if !v.contains(t) {
v.push(t);
}
}
v.join(", ")
}
}
#[derive(Debug, Default)]
pub struct Query {
classes: Vec<String>,
labels: Vec<String>,
writes_regs: Vec<String>,
set_regs: Vec<String>,
from_stack: bool,
no_clobber: Vec<String>,
reads_regs: Vec<String>,
max_stack_delta: Option<i64>,
max_side_effects: Option<usize>,
max_insns: Option<usize>,
terminators: Vec<TermQuery>,
search: Option<SeqPattern>,
}
#[derive(Debug, Default, Clone)]
pub struct QuerySpec<'a> {
pub class: Option<&'a str>,
pub label: Option<&'a str>,
pub writes_reg: Option<&'a str>,
pub set_reg: Option<&'a str>,
pub from_stack: bool,
pub no_clobber: Option<&'a str>,
pub reads_reg: Option<&'a str>,
pub max_stack_delta: Option<i64>,
pub max_side_effects: Option<usize>,
pub max_insns: Option<usize>,
pub terminator: Option<&'a str>,
pub search: Option<&'a str>,
pub pivot: bool,
}
pub const PIVOT_LABEL: &str = "stack-pivot";
impl Query {
pub fn parse(spec: &QuerySpec<'_>) -> Result<Query, String> {
let valid: Vec<&str> = [
rf_classify::Class::RegWrite,
rf_classify::Class::StackPivot,
rf_classify::Class::MemRead,
rf_classify::Class::MemWrite,
rf_classify::Class::Arithmetic,
rf_classify::Class::Syscall,
rf_classify::Class::Dispatcher,
rf_classify::Class::Other,
]
.iter()
.map(|c| c.name())
.collect();
let split_names = |v: Option<&str>| -> Vec<String> {
v.map(|s| {
s.split(LIST_SEPARATORS)
.map(str::trim)
.filter(|x| !x.is_empty())
.map(str::to_string)
.collect()
})
.unwrap_or_default()
};
let classes = split_names(spec.class);
let mut labels = split_names(spec.label);
for (flag, values) in [("--class", &classes), ("--label", &labels)] {
for v in values {
if !valid.contains(&v.as_str()) {
return Err(format!(
"invalid {flag} value {v:?}; valid values are {}",
valid.join(", ")
));
}
}
}
if spec.pivot && !labels.iter().any(|l| l == PIVOT_LABEL) {
labels.push(PIVOT_LABEL.to_string());
}
let mut terminators = Vec::new();
for t in split_names(spec.terminator) {
let t = t.to_ascii_lowercase();
terminators.push(TermQuery::parse(&t).ok_or_else(|| {
format!(
"invalid --terminator value {t:?}; valid values are {}",
TermQuery::vocabulary()
)
})?);
}
Ok(Query {
classes,
labels,
writes_regs: split_list(spec.writes_reg),
set_regs: split_list(spec.set_reg),
from_stack: spec.from_stack,
no_clobber: split_list(spec.no_clobber),
reads_regs: split_list(spec.reads_reg),
max_stack_delta: spec.max_stack_delta,
max_side_effects: spec.max_side_effects,
max_insns: spec.max_insns,
terminators,
search: spec.search.map(SeqPattern::parse).transpose()?,
})
}
pub fn is_empty(&self) -> bool {
self.classes.is_empty()
&& self.labels.is_empty()
&& self.writes_regs.is_empty()
&& self.set_regs.is_empty()
&& !self.from_stack
&& self.no_clobber.is_empty()
&& self.reads_regs.is_empty()
&& self.max_stack_delta.is_none()
&& self.max_side_effects.is_none()
&& self.max_insns.is_none()
&& self.terminators.is_empty()
&& self.search.is_none()
}
pub fn matches(&self, c: &Classification, insns: &[&str]) -> bool {
if !self.classes.is_empty() && !self.classes.iter().any(|n| n == c.primary.name()) {
return false;
}
if !self.labels.is_empty()
&& !self
.labels
.iter()
.any(|n| c.labels.iter().any(|l| l.name() == n))
{
return false;
}
if !self
.writes_regs
.iter()
.all(|r| c.regs_written.iter().any(|w| w == r))
{
return false;
}
if !self.set_regs.iter().all(|r| c.sets_reg(r)) {
return false;
}
if self.from_stack {
let anchor = if self.set_regs.is_empty() {
&self.writes_regs
} else {
&self.set_regs
};
let ok = if anchor.is_empty() {
!c.regs_from_stack.is_empty()
} else {
anchor.iter().all(|r| c.reg_from_stack(r))
};
if !ok {
return false;
}
}
if c.clobbers_any(&self.no_clobber) {
return false;
}
if !self.reads_regs.iter().all(|r| reads_reg(c, r)) {
return false;
}
if let Some(limit) = self.max_stack_delta {
match c.stack_delta {
Some(d) if d <= limit => {}
_ => return false,
}
}
if let Some(limit) = self.max_side_effects {
if c.side_effects > limit {
return false;
}
}
if let Some(limit) = self.max_insns {
if insns.len() > limit {
return false;
}
}
if !self.terminators.is_empty() && !self.terminators.iter().any(|t| t.matches(c)) {
return false;
}
if let Some(p) = &self.search {
if !p.matches(insns) {
return false;
}
}
true
}
}
fn reads_reg(c: &Classification, reg: &str) -> bool {
c.reads_reg(reg)
}
#[cfg(test)]
mod tests {
use super::*;
use rf_classify::Transfer;
fn seq(p: &str) -> SeqPattern {
SeqPattern::parse(p).expect("pattern compiles")
}
fn classified_ret() -> Classification {
let g = rf_scan::Gadget {
vaddr: 0x1000,
bytes: vec![0xc3],
insns: vec!["ret".to_string()],
delay_slot: false,
prev: None,
table: rf_scan::TableKind::Rop,
};
rf_classify::classify(&g, rf_core::Arch::X64)
}
#[test]
fn search_matches_a_contiguous_subsequence() {
let p = seq("pop rdi; ret");
assert!(p.matches(&["pop rdi", "ret"]));
assert!(p.matches(&["xor eax, eax", "pop rdi", "ret"]));
assert!(!p.matches(&["pop rdi", "pop rsi", "ret"]));
assert!(!p.matches(&["ret"]));
}
#[test]
fn search_wildcards_and_metacharacters() {
assert!(seq("pop r?i; ret").matches(&["pop rdi", "ret"]));
assert!(!seq("pop r?i; ret").matches(&["pop rsp", "ret"]));
assert!(seq("%; ret").matches(&["anything at all", "ret"]));
assert!(seq("mov %, rax; ret").matches(&["mov rbx, rax", "ret"]));
assert!(seq("mov [rbx+8], rax").matches(&["mov [rbx+8], rax"]));
assert!(!seq("mov [rbx+8], rax").matches(&["mov [rbx+9], rax"]));
assert!(seq("POP rdi").matches(&["pop rdi"]));
}
#[test]
fn search_rejects_an_empty_pattern() {
assert!(SeqPattern::parse(" ; ; ").is_err());
assert!(SeqPattern::parse("").is_err());
}
#[test]
fn terminator_vocabulary_accepts_both_spellings() {
assert_eq!(TermQuery::parse("ret"), Some(TermQuery::Kind("ret")));
assert_eq!(
TermQuery::parse("bare-ret"),
Some(TermQuery::Class(TerminatorClass::Ret))
);
assert_eq!(
TermQuery::parse("jmp-reg"),
Some(TermQuery::Class(TerminatorClass::JmpReg))
);
assert_eq!(TermQuery::parse("jmp"), Some(TermQuery::Kind("jmp")));
assert_eq!(TermQuery::parse("nonsense"), None);
let v = TermQuery::vocabulary();
for w in [
"ret", "jmp", "call", "syscall", "bare-ret", "ret-imm", "far",
] {
assert!(v.contains(w), "{w} missing from {v}");
}
}
#[test]
fn pivot_is_the_stack_pivot_label() {
let q = Query::parse(&QuerySpec {
pivot: true,
..Default::default()
})
.unwrap();
assert!(!q.is_empty());
assert_eq!(q.labels, vec![PIVOT_LABEL.to_string()]);
}
#[test]
fn register_names_lose_their_sigil() {
assert_eq!(norm_reg(" $RDI "), "rdi");
assert_eq!(norm_reg("%eax"), "eax");
assert_eq!(split_list(Some("rsi, rdx")), vec!["rsi", "rdx"]);
assert_eq!(split_list(Some("")), Vec::<String>::new());
}
#[test]
fn an_unknown_stack_delta_never_satisfies_a_bound() {
let q = Query::parse(&QuerySpec {
max_stack_delta: Some(64),
..Default::default()
})
.unwrap();
let mut c = classified_ret();
c.stack_delta = None;
assert!(!q.matches(&c, &["ret"]), "None must not read as 0");
c.stack_delta = Some(64);
assert!(q.matches(&c, &["ret"]));
c.stack_delta = Some(65);
assert!(!q.matches(&c, &["ret"]));
}
#[test]
fn register_flags_are_comma_separated_all_of_lists() {
let q = Query::parse(&QuerySpec {
set_reg: Some("rdi, RSI"),
reads_reg: Some("rax|rcx"),
..Default::default()
})
.unwrap();
assert_eq!(q.set_regs, vec!["rdi".to_string(), "rsi".to_string()]);
assert_eq!(q.reads_regs, vec!["rax".to_string(), "rcx".to_string()]);
let mut c = classified_ret();
c.sets = vec!["rdi".to_string()];
assert!(
!q.matches(&c, &["ret"]),
"ALL of the named registers must be set, not any of them"
);
c.sets = vec!["rdi".to_string(), "rsi".to_string()];
c.regs_read = vec!["rax".to_string(), "rcx".to_string()];
assert!(q.matches(&c, &["ret"]));
let one = Query::parse(&QuerySpec {
set_reg: Some("rdi"),
..Default::default()
})
.unwrap();
assert_eq!(one.set_regs, vec!["rdi".to_string()]);
}
#[test]
fn from_stack_requires_every_named_register_to_come_off_the_payload() {
let q = Query::parse(&QuerySpec {
set_reg: Some("rdi,rsi"),
from_stack: true,
..Default::default()
})
.unwrap();
let mut c = classified_ret();
c.sets = vec!["rdi".to_string(), "rsi".to_string()];
c.regs_from_stack = vec!["rdi".to_string()];
c.transfers = vec![Transfer {
dst: rf_classify::ValueDst::Register {
reg: "rdi".to_string(),
},
src: rf_classify::ValueSrc::Stack { offset: Some(0) },
needs: Vec::new(),
rmw: false,
width: Some(8),
}];
assert!(
!q.matches(&c, &["ret"]),
"rsi is set but not from the stack, so the gadget must not match"
);
}
#[test]
fn invalid_values_name_the_vocabulary() {
let err = Query::parse(&QuerySpec {
terminator: Some("returns"),
..Default::default()
})
.unwrap_err();
assert!(err.contains("--terminator"), "{err}");
assert!(err.contains("syscall"), "{err}");
let err = Query::parse(&QuerySpec {
class: Some("pivot"),
..Default::default()
})
.unwrap_err();
assert!(err.contains("stack-pivot"), "{err}");
}
}