A formal framework to design and prove trustworthy memory controllers
Open Access
- 14 November 2023
- journal article
- research article
- Published by Springer Nature in Real-Time Systems
- Vol. 59 (4) , 664-704
Abstract
In order to prove conformance to memory standards and bound memory access latency, recently proposed real-time DRAM controllers rely on paper and pencil proofs, which can be troubling: they are difficult to read and review, they are often shown only partially and/or rely on abstractions for the sake of conciseness, and they can easily diverge from the controller implementation, as no formal link is established between both. We propose a new framework written in Coq, in which we model a DRAM controller and its expected behaviour as a formal specification. The trustworthiness in our solution is two-fold: (1) proofs that are typically done on paper and pencil are now done in Coq and thus certified by its kernel, and (2) the reviewer’s job develops into making sure that the formal specification matches the standards—instead of performing a thorough check of the mathematical formalism. Our framework provides a generic DRAM model capturing a set of controller properties as proof obligations, which all implementations must comply with. We focus on properties related to the assertiveness that timing constraints are respected, every incoming request is handled in bounded time, and the DRAM command protocol is respected. We refine our specification with two implementations based on widely-known arbitration policies—First-in First-Out (FIFO) and Time-Division Multiplexing (TDM). We extract proved code from our model and use it as a “trusted core” on a cycle-accurate DRAM simulator.Keywords
Funding Information
- LabeX Digicosme (ANR11IDEX000302)
This publication has 36 references indexed in Scilit:
- MEDUSA: A Predictable and High-Performance DRAM Controller for Multicore Based Embedded Systems2015
- Parallelism-Aware Memory Interference Delay Analysis for COTS Multicore Systems2015
- A framework for scheduling DRAM memory accesses for multi-core mixed-time critical systems2015
- A Dual-Criticality Memory Controller (DCmc): Proposal and Evaluation of a Space Case Study2014
- Worst Case Analysis of DRAM Latency in Multi-requestor Systems2013
- PRET DRAM controller2011
- Making DRAM refresh predictableReal-Time Systems, 2011
- Memory access schedulingACM SIGARCH Computer Architecture News, 2000
- LavaACM SIGPLAN Notices, 1998
- Uppaal in a nutshellInternational Journal on Software Tools for Technology Transfer, 1997