1use std::collections::HashMap;
40use std::convert::TryFrom;
41use std::fmt;
42use std::ops::Range;
43use std::sync::Arc;
44
45use crate::bitvector::BV;
46use crate::error::ExecError;
47use crate::ir;
48use crate::ir::Val;
49use crate::log;
50use crate::probe;
51use crate::smt::smtlib::{bits64, Def, Exp};
52use crate::smt::{Event, SmtResult, Solver, Sym};
53
54pub type Address = u64;
56
57pub trait CustomRegion<B> {
58 fn read(
59 &self,
60 read_kind: Val<B>,
61 address: Address,
62 bytes: u32,
63 solver: &mut Solver<B>,
64 tag: bool,
65 ) -> Result<Val<B>, ExecError>;
66
67 fn write(
68 &mut self,
69 write_kind: Val<B>,
70 address: Address,
71 data: Val<B>,
72 solver: &mut Solver<B>,
73 tag: Option<Val<B>>,
74 ) -> Result<Val<B>, ExecError>;
75
76 fn initial_value(&self, address: Address, bytes: u32) -> Option<B>;
77
78 fn memory_kind(&self) -> &'static str;
83
84 fn clone_dyn(&self) -> Box<dyn Send + Sync + CustomRegion<B>>;
89}
90
91pub enum Region<B> {
92 Constrained(Range<Address>, Arc<dyn Send + Sync + Fn(&mut Solver<B>) -> Sym>),
97 Symbolic(Range<Address>),
99 SymbolicCode(Range<Address>),
101 Concrete(Range<Address>, HashMap<Address, u8>),
103 Custom(Range<Address>, Box<dyn Send + Sync + CustomRegion<B>>),
105}
106
107impl<B> Clone for Region<B> {
108 fn clone(&self) -> Self {
109 use Region::*;
110 match self {
111 Constrained(r, contents) => Constrained(r.clone(), contents.clone()),
112 Symbolic(r) => Symbolic(r.clone()),
113 SymbolicCode(r) => SymbolicCode(r.clone()),
114 Concrete(r, contents) => Concrete(r.clone(), contents.clone()),
115 Custom(r, contents) => Custom(r.clone(), contents.clone_dyn()),
116 }
117 }
118}
119
120pub enum SmtKind {
121 ReadData,
122 ReadInstr,
123 WriteData,
124}
125
126impl<B> fmt::Debug for Region<B> {
127 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
128 use Region::*;
129 match self {
130 Constrained(r, _) => write!(f, "Constrained({:?}, <closure>)", r),
131 Symbolic(r) => write!(f, "Symbolic({:?})", r),
132 SymbolicCode(r) => write!(f, "SymbolicCode({:?})", r),
133 Concrete(r, locs) => write!(f, "Concrete({:?}, {:?})", r, locs),
134 Custom(r, _) => write!(f, "Custom({:?}, <trait object>)", r),
135 }
136 }
137}
138
139impl<B> Region<B> {
140 fn memory_kind(&self) -> &'static str {
141 match self {
142 Region::Constrained(_, _) => "constrained",
143 Region::Symbolic(_) => "symbolic",
144 Region::SymbolicCode(_) => "symbolic code",
145 Region::Concrete(_, _) => "concrete",
146 Region::Custom(_, contents) => contents.memory_kind(),
147 }
148 }
149
150 fn region_range(&self) -> &Range<Address> {
151 match self {
152 Region::Constrained(r, _) => r,
153 Region::Symbolic(r) => r,
154 Region::SymbolicCode(r) => r,
155 Region::Concrete(r, _) => r,
156 Region::Custom(r, _) => r,
157 }
158 }
159}
160
161pub trait MemoryCallbacks<B>: fmt::Debug + MemoryCallbacksClone<B> + Send + Sync {
168 fn symbolic_read(
169 &self,
170 regions: &[Region<B>],
171 solver: &mut Solver<B>,
172 value: &Val<B>,
173 read_kind: &Val<B>,
174 address: &Val<B>,
175 bytes: u32,
176 tag: &Option<Val<B>>,
177 );
178 #[allow(clippy::too_many_arguments)]
179 fn symbolic_write(
180 &mut self,
181 regions: &[Region<B>],
182 solver: &mut Solver<B>,
183 value: Sym,
184 write_kind: &Val<B>,
185 address: &Val<B>,
186 data: &Val<B>,
187 bytes: u32,
188 tag: &Option<Val<B>>,
189 );
190}
191
192pub trait MemoryCallbacksClone<B> {
193 fn clone_box(&self) -> Box<dyn MemoryCallbacks<B>>;
194}
195
196impl<B, T> MemoryCallbacksClone<B> for T
197where
198 T: 'static + MemoryCallbacks<B> + Clone,
199{
200 fn clone_box(&self) -> Box<dyn MemoryCallbacks<B>> {
201 Box::new(self.clone())
202 }
203}
204
205impl<B> Clone for Box<dyn MemoryCallbacks<B>> {
206 fn clone(&self) -> Box<dyn MemoryCallbacks<B>> {
207 self.clone_box()
208 }
209}
210
211fn make_bv_bit_pair<B>(left: Val<B>, right: Val<B>) -> Val<B> {
212 let mut fields = HashMap::new();
213 fields.insert(ir::BV_BIT_LEFT, left);
214 fields.insert(ir::BV_BIT_RIGHT, right);
215 Val::Struct(fields)
216}
217
218#[derive(Clone, Debug, Default)]
219pub struct Memory<B> {
220 regions: Vec<Region<B>>,
221 client_info: Option<Box<dyn MemoryCallbacks<B>>>,
222}
223
224static DEFAULT_MEMORY_KIND: &str = "default";
225
226impl<B: BV> Memory<B> {
227 pub fn new() -> Self {
228 Memory { regions: Vec::new(), client_info: None }
229 }
230
231 pub fn kind_at(&self, addr: Address) -> &'static str {
232 for region in &self.regions {
233 if region.region_range().contains(&addr) {
234 return region.memory_kind();
235 }
236 }
237 DEFAULT_MEMORY_KIND
238 }
239
240 pub fn log(&self) {
241 for region in &self.regions {
242 match region {
243 Region::Constrained(range, _) => {
244 log!(log::MEMORY, &format!("Memory range: [0x{:x}, 0x{:x}) constrained", range.start, range.end))
245 }
246 Region::Symbolic(range) => {
247 log!(log::MEMORY, &format!("Memory range: [0x{:x}, 0x{:x}) symbolic", range.start, range.end))
248 }
249 Region::SymbolicCode(range) => {
250 log!(log::MEMORY, &format!("Memory range: [0x{:x}, 0x{:x}) symbolic code", range.start, range.end))
251 }
252 Region::Concrete(range, _) => {
253 log!(log::MEMORY, &format!("Memory range: [0x{:x}, 0x{:x}) concrete", range.start, range.end))
254 }
255 Region::Custom(range, contents) => log!(
256 log::MEMORY,
257 &format!(
258 "Memory range: [0x{:x}, 0x{:x}) custom {}",
259 range.start,
260 range.end,
261 contents.memory_kind()
262 )
263 ),
264 }
265 }
266 }
267
268 pub fn in_custom_region(&self, addr: Address) -> Option<&dyn CustomRegion<B>> {
269 for region in &self.regions {
270 match region {
271 Region::Custom(range, mem) if range.contains(&addr) => return Some(mem.as_ref()),
272 _ => (),
273 }
274 }
275 None
276 }
277
278 pub fn add_region(&mut self, region: Region<B>) {
279 self.regions.push(region)
280 }
281
282 pub fn add_symbolic_region(&mut self, range: Range<Address>) {
283 self.regions.push(Region::Symbolic(range))
284 }
285
286 pub fn add_symbolic_code_region(&mut self, range: Range<Address>) {
287 self.regions.push(Region::SymbolicCode(range))
288 }
289
290 pub fn add_concrete_region(&mut self, range: Range<Address>, contents: HashMap<Address, u8>) {
291 self.regions.push(Region::Concrete(range, contents))
292 }
293
294 pub fn add_zero_region(&mut self, range: Range<Address>) {
295 self.regions.push(Region::Concrete(range, HashMap::new()))
296 }
297
298 pub fn set_client_info(&mut self, info: Box<dyn MemoryCallbacks<B>>) {
299 self.client_info = Some(info);
300 }
301
302 pub fn write_byte(&mut self, address: Address, byte: u8) {
303 for region in &mut self.regions {
304 match region {
305 Region::Concrete(range, contents) if range.contains(&address) => {
306 contents.insert(address, byte);
307 return;
308 }
309 _ => (),
310 }
311 }
312 self.regions.push(Region::Concrete(address..address, vec![(address, byte)].into_iter().collect()))
313 }
314
315 fn read_initial_byte(&self, address: Address) -> Result<u8, ExecError> {
316 use Region::*;
317 for region in &self.regions {
318 match region {
319 Constrained(range, _) | Symbolic(range) | SymbolicCode(range) if range.contains(&address) => {
320 return Err(ExecError::BadRead("symbolic initial byte"))
321 }
322 Concrete(range, contents) if range.contains(&address) => {
323 return Ok(contents.get(&address).copied().unwrap_or(0))
324 }
325 Custom(range, contents) if range.contains(&address) => {
326 return contents
327 .initial_value(address, 1)
328 .map(B::lower_u8)
329 .ok_or(ExecError::BadRead("read of initial byte from custom region failed"))
330 }
331 _ => (),
332 }
333 }
334 Err(ExecError::BadRead("symbolic initial byte (no region)"))
335 }
336
337 pub fn read_initial(&self, address: Address, bytes: u32) -> Result<Val<B>, ExecError> {
338 let mut byte_vec: Vec<u8> = Vec::with_capacity(bytes as usize);
339 for i in address..(address + u64::from(bytes)) {
340 byte_vec.push(self.read_initial_byte(i)?)
341 }
342
343 reverse_endianness(&mut byte_vec);
344
345 if byte_vec.len() <= 8 {
346 Ok(Val::Bits(B::from_bytes(&byte_vec)))
347 } else {
348 Err(ExecError::BadRead("initial read greater than 8 bytes"))
349 }
350 }
351
352 fn check_overlap(&self, address: Sym, error: ExecError, solver: &mut Solver<B>) -> Result<(), ExecError> {
353 use Exp::*;
354 use SmtResult::*;
355
356 let mut region_constraints = Vec::new();
357
358 for region in &self.regions {
359 let Range { start, end } = region.region_range();
360
361 region_constraints.push(And(
362 Box::new(Bvule(Box::new(bits64(*start, 64)), Box::new(Var(address)))),
363 Box::new(Bvult(Box::new(Var(address)), Box::new(bits64(*end, 64)))),
364 ))
365 }
366
367 if let Some(r) = region_constraints.pop() {
368 let constraint = region_constraints.drain(..).fold(r, |r1, r2| Or(Box::new(r1), Box::new(r2)));
369 match solver.check_sat_with(&constraint) {
370 Sat => {
371 probe::taint_info(log::MEMORY, address, None, solver);
372 return Err(error);
373 }
374 Unknown => return Err(ExecError::Z3Unknown),
375 Unsat => (),
376 }
377 }
378
379 Ok(())
380 }
381
382 pub fn read(
391 &self,
392 read_kind: Val<B>,
393 address: Val<B>,
394 bytes: Val<B>,
395 solver: &mut Solver<B>,
396 tag: bool,
397 ) -> Result<Val<B>, ExecError> {
398 log!(log::MEMORY, &format!("Read: {:?} {:?} {:?} {:?}", read_kind, address, bytes, tag));
399
400 if let Val::I128(bytes) = bytes {
401 let bytes = u32::try_from(bytes).expect("Bytes did not fit in u32 in memory read");
402
403 match address {
404 Val::Bits(concrete_addr) => {
405 for region in &self.regions {
406 match region {
407 Region::Constrained(range, generator) if range.contains(&concrete_addr.lower_u64()) => {
408 return read_constrained(
409 range,
410 generator.as_ref(),
411 read_kind,
412 concrete_addr.lower_u64(),
413 bytes,
414 solver,
415 tag,
416 region.memory_kind(),
417 )
418 }
419
420 Region::Symbolic(range) if range.contains(&concrete_addr.lower_u64()) => {
421 return self.read_symbolic(read_kind, address, bytes, solver, tag, region.memory_kind())
422 }
423
424 Region::SymbolicCode(range) if range.contains(&concrete_addr.lower_u64()) => {
425 return self.read_symbolic(read_kind, address, bytes, solver, tag, region.memory_kind())
426 }
427
428 Region::Concrete(range, contents) if range.contains(&concrete_addr.lower_u64()) => {
429 return read_concrete(
430 contents,
431 read_kind,
432 concrete_addr.lower_u64(),
433 bytes,
434 solver,
435 tag,
436 region.memory_kind(),
437 )
438 }
439
440 Region::Custom(range, contents) if range.contains(&concrete_addr.lower_u64()) => {
441 return contents.read(read_kind, concrete_addr.lower_u64(), bytes, solver, tag)
442 }
443
444 _ => continue,
445 }
446 }
447
448 self.read_symbolic(read_kind, address, bytes, solver, tag, DEFAULT_MEMORY_KIND)
449 }
450
451 Val::Symbolic(symbolic_addr) => {
452 self.check_overlap(symbolic_addr, ExecError::BadRead("possible symbolic address overlap"), solver)?;
453 self.read_symbolic(read_kind, address, bytes, solver, tag, DEFAULT_MEMORY_KIND)
454 }
455
456 _ => Err(ExecError::Type("Non bitvector address in read".to_string())),
457 }
458 } else {
459 Err(ExecError::SymbolicLength("read_symbolic"))
460 }
461 }
462
463 pub fn write(
464 &mut self,
465 write_kind: Val<B>,
466 address: Val<B>,
467 data: Val<B>,
468 solver: &mut Solver<B>,
469 tag: Option<Val<B>>,
470 ) -> Result<Val<B>, ExecError> {
471 log!(log::MEMORY, &format!("Write: {:?} {:?} {:?} {:?}", write_kind, address, data, tag));
472
473 match address {
474 Val::Bits(concrete_addr) => {
475 for region in self.regions.iter_mut() {
476 match region {
477 Region::Custom(range, contents) if range.contains(&concrete_addr.lower_u64()) => {
478 return contents.write(write_kind, concrete_addr.lower_u64(), data, solver, tag)
479 }
480
481 _ => continue,
482 }
483 }
484
485 self.write_symbolic(write_kind, address, data, solver, tag, DEFAULT_MEMORY_KIND)
486 }
487
488 Val::Symbolic(symbolic_addr) => {
489 self.check_overlap(symbolic_addr, ExecError::BadWrite("possible symbolic address overlap"), solver)?;
490 self.write_symbolic(write_kind, address, data, solver, tag, DEFAULT_MEMORY_KIND)
491 }
492
493 _ => Err(ExecError::Type("Non bitvector address in write".to_string())),
494 }
495 }
496
497 fn read_symbolic(
502 &self,
503 read_kind: Val<B>,
504 address: Val<B>,
505 bytes: u32,
506 solver: &mut Solver<B>,
507 tag: bool,
508 kind: &'static str,
509 ) -> Result<Val<B>, ExecError> {
510 use crate::smt::smtlib::*;
511
512 let value = solver.fresh();
513 solver.add(Def::DeclareConst(value, Ty::BitVec(8 * bytes)));
514
515 let tag_value = if tag {
516 let v = solver.fresh();
517 solver.add(Def::DeclareConst(v, Ty::BitVec(1)));
518 Some(v)
519 } else {
520 None
521 };
522 let tag_ir_value = tag_value.map(Val::Symbolic);
523 match &self.client_info {
524 Some(c) => c.symbolic_read(
525 &self.regions,
526 solver,
527 &Val::Symbolic(value),
528 &read_kind,
529 &address,
530 bytes,
531 &tag_ir_value,
532 ),
533 None => (),
534 };
535 solver.add_event(Event::ReadMem {
536 value: Val::Symbolic(value),
537 read_kind,
538 address,
539 bytes,
540 tag_value: tag_ir_value.clone(),
541 kind,
542 });
543
544 log!(log::MEMORY, &format!("Read symbolic: {} {:?}", value, tag_value));
545
546 let return_value = match tag_ir_value {
547 Some(v) => make_bv_bit_pair(Val::Symbolic(value), v),
548 None => Val::Symbolic(value),
549 };
550 Ok(return_value)
551 }
552
553 fn write_symbolic(
560 &mut self,
561 write_kind: Val<B>,
562 address: Val<B>,
563 data: Val<B>,
564 solver: &mut Solver<B>,
565 tag: Option<Val<B>>,
566 kind: &'static str,
567 ) -> Result<Val<B>, ExecError> {
568 use crate::smt::smtlib::*;
569
570 let data_length = crate::primop::length_bits(&data, solver)?;
571 if data_length % 8 != 0 {
572 return Err(ExecError::Type(format!("write_symbolic {:?}", &data_length)));
573 };
574 let bytes = data_length / 8;
575
576 let value = solver.fresh();
577 solver.add(Def::DeclareConst(value, Ty::Bool));
578 match &mut self.client_info {
579 Some(c) => c.symbolic_write(&self.regions, solver, value, &write_kind, &address, &data, bytes, &tag),
580 None => (),
581 };
582 solver.add_event(Event::WriteMem { value, write_kind, address, data, bytes, tag_value: tag, kind });
583
584 Ok(Val::Symbolic(value))
585 }
586
587 pub fn smt_address_constraint(
588 &self,
589 address: &Exp,
590 bytes: u32,
591 kind: SmtKind,
592 solver: &mut Solver<B>,
593 tag: Option<&Exp>,
594 ) -> Exp {
595 smt_address_constraint(&self.regions, address, bytes, kind, solver, tag)
596 }
597}
598
599pub fn smt_address_constraint<B: BV>(
600 regions: &[Region<B>],
601 address: &Exp,
602 bytes: u32,
603 kind: SmtKind,
604 solver: &mut Solver<B>,
605 tag: Option<&Exp>,
606) -> Exp {
607 use crate::smt::smtlib::Exp::*;
608 let addr_var = match address {
609 Var(v) => *v,
610 _ => {
611 let v = solver.fresh();
612 solver.add(Def::DefineConst(v, address.clone()));
613 v
614 }
615 };
616 regions
617 .iter()
618 .filter(|r| match kind {
619 SmtKind::ReadData => true,
620 SmtKind::ReadInstr => matches!(r, Region::SymbolicCode(_)),
621 SmtKind::WriteData => matches!(r, Region::Symbolic(_)),
622 })
623 .map(|r| (r.region_range(), matches!(r, Region::Symbolic(_))))
624 .filter(|(r, _k)| r.end - r.start >= bytes as u64)
625 .map(|(r, k)| {
626 let in_range = And(
627 Box::new(Bvule(Box::new(bits64(r.start, 64)), Box::new(Var(addr_var)))),
628 Box::new(Bvult(
630 Box::new(Bvadd(
631 Box::new(ZeroExtend(65, Box::new(Var(addr_var)))),
632 Box::new(ZeroExtend(65, Box::new(bits64(bytes as u64, 64)))),
633 )),
634 Box::new(ZeroExtend(65, Box::new(bits64(r.end, 64)))),
635 )),
636 );
637 if let (false, Some(tag)) = (k, tag) {
639 And(Box::new(in_range), Box::new(Eq(Box::new(tag.clone()), Box::new(bits64(0, 1)))))
640 } else {
641 in_range
642 }
643 })
644 .fold(Bool(false), |acc, e| match acc {
645 Bool(false) => e,
646 _ => Or(Box::new(acc), Box::new(e)),
647 })
648}
649
650fn reverse_endianness(bytes: &mut [u8]) {
651 if bytes.len() <= 2 {
652 bytes.reverse()
653 } else {
654 let (bytes_upper, bytes_lower) = bytes.split_at_mut(bytes.len() / 2);
655 reverse_endianness(bytes_upper);
656 reverse_endianness(bytes_lower);
657 bytes.rotate_left(bytes.len() / 2)
658 }
659}
660
661fn read_constrained<B: BV>(
662 range: &Range<Address>,
663 generator: &(dyn Fn(&mut Solver<B>) -> Sym),
664 read_kind: Val<B>,
665 address: Address,
666 bytes: u32,
667 solver: &mut Solver<B>,
668 tag: bool,
669 kind: &'static str,
670) -> Result<Val<B>, ExecError> {
671 let region = generator(solver);
672 if address == range.start && address + bytes as u64 == range.end {
673 solver.add_event(Event::ReadMem {
674 value: Val::Symbolic(region),
675 read_kind,
676 address: Val::Bits(B::from_u64(address)),
677 bytes,
678 tag_value: None,
679 kind,
680 });
681 if tag {
682 Ok(make_bv_bit_pair(Val::Symbolic(region), Val::Bits(B::zeros(1))))
683 } else {
684 Ok(Val::Symbolic(region))
685 }
686 } else {
687 Err(ExecError::BadRead("constrained read address is not within bounds"))
688 }
689}
690
691fn read_concrete<B: BV>(
692 region: &HashMap<Address, u8>,
693 read_kind: Val<B>,
694 address: Address,
695 bytes: u32,
696 solver: &mut Solver<B>,
697 tag: bool,
698 kind: &'static str,
699) -> Result<Val<B>, ExecError> {
700 let mut byte_vec: Vec<u8> = Vec::with_capacity(bytes as usize);
701 for i in address..(address + u64::from(bytes)) {
702 byte_vec.push(*region.get(&i).unwrap_or(&0))
703 }
704
705 reverse_endianness(&mut byte_vec);
706
707 if byte_vec.len() <= 8 {
708 log!(log::MEMORY, &format!("Read concrete: {:?}", byte_vec));
709
710 let value = Val::Bits(B::from_bytes(&byte_vec));
711 solver.add_event(Event::ReadMem {
712 value,
713 read_kind,
714 address: Val::Bits(B::from_u64(address)),
715 bytes,
716 tag_value: None,
717 kind,
718 });
719 if tag {
720 Ok(make_bv_bit_pair(Val::Bits(B::from_bytes(&byte_vec)), Val::Bits(B::zeros(1))))
721 } else {
722 Ok(Val::Bits(B::from_bytes(&byte_vec)))
723 }
724 } else {
725 Err(ExecError::BadRead("concrete read more than 8 bytes"))
727 }
728}