serval/toyrv.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Verification of Systems Code\n",
    "\n",
    "Previously we looked at the verification of Verilog hardware implementations. In this post, we will be looking at the verification of firmware or systems code. Here the hardware implementation is abstracted with Instruction Level Abstraction (ILA). This allows us to make complex verification problems more tractable.\n",
    "\n",
    "ILAS refers to a level of abstraction in computer systems design and analysis that focuses on the behavior and functionality of individual instructions within a processor or microarchitecture. It involves representing and reasoning about instructions as fundamental units of computation, abstracting away lower-level details and complexities. At the instruction level, the emphasis is on understanding the functionality and effects of instructions, including their operation, data flow, dependencies, and control flow. ILA provides a higher-level perspective that allows for the analysis of programs and systems without getting into the intricacies of the underlying hardware implementation."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Setup\n",
    "\n",
    "We will be using the same environment with Jupyter Notebook with the Racket extension called Serval. You can use the same steps that we discussed in the [initial post](https://archfx.github.io/posts/2023/04/racketutes1/) of this series for the configuration but with the following docker container.\n",
    "\n",
    "```shell\n",
    "docker pull archfx/serval\n",
    "```\n",
    "<p align=\"center\"><a href=\"https://hub.docker.com/r/archfx/serval\"><img src=\"https://dockerico.blankenship.io/image/archfx/serval\"/></a></p>\n",
    "\n",
    "otherthan that every step for the environment stays the same as the [previous setup](https://archfx.github.io/posts/2023/04/racketutes1/). In addition to Racket, Rosette, Z3 and Serval this container consists of RISC-V tool-chain components which will allow us to compile and verify RISC-V systems code which we will look in future post.\n",
    "\n",
    "This post as a Jupyter Notebook is available [here]().\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Serval\n",
    "\n",
    "As I mentioned earlier, Serval is a Racket extension built with Rosette that can act as a processor interpreter. We can define the ILA for the processor that your firmware is built for, with Serval. Then, we can compile the firmware, obtain the binary and using Serval we can uplift the systems code into Racket supporting syntaxes. There are few things to note here, Serval does not support concurrent codes and codes with unbounded loops. I don't think these are limitations, since as verification engineers, we need to be creative to solve these kinds of issues."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ToyRISC Example\n",
    "\n",
    "Serval provides an example interpreter and state-machine refinement with safety property verification for a sample processor which is based on a sample instruction set called ToyRISC. We will be looking at each of the components of this example. Finally, we will make some modifications to the code, such that it violates the expected behavior."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we start by importing `rosette` ,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "#lang iracket/lang #:require rosette"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we need to import the serval definitions,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "; import serval functions with prefix \"serval:\"\n",
    "(require\n",
    "  serval/lib/unittest\n",
    "  rackunit/text-ui\n",
    "  (prefix-in serval:\n",
    "    (combine-in serval/lib/core\n",
    "                serval/spec/refinement\n",
    "                serval/spec/ni)))\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interpriter\n",
    "\n",
    "An interpreter is a computer program or software component that reads and executes code or instructions directly without the need for prior compilation. It takes source code written in a high-level programming language and translates it into machine code or performs the instructions directly on the fly. Interpreters work line by line, executing statements in a sequential manner."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ToyRISC Interpreter\n",
    "\n",
    "The interpreter defines the operations available in the instruction set. This is similar to an implementation of an instruction set simulator. In the case of the ToyRISC example, the instruction set only contains 5 instructions of `ret`,`bnez`,`sgtz`,`sltz` and `li`. Basically, the interpreter will interpret the binary of the firmware for Rosette for formal proofs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "#| ToyRISC Interpreter |#\n",
    "\n",
    "; cpu state: program counter and integer registers\n",
    "(struct cpu (pc regs) #:mutable #:transparent)\n",
    "\n",
    "; interpret a program from a given cpu state\n",
    "(define (interpret c program)\n",
    "  ; Use Serval's \"split-pc\" symbolic optimization\n",
    "  (serval:split-pc (cpu pc) c\n",
    "    ; fetch an instruction to execute\n",
    "    (define insn (fetch c program))\n",
    "    ; decode an instruction into (opcode, rd, rs, imm)\n",
    "    (match insn\n",
    "      [(list opcode rd rs imm)\n",
    "          ; execute the instruction\n",
    "          (execute c opcode rd rs imm)\n",
    "          ; recursively interpret a program until \"ret\"\n",
    "          (when (not (equal? opcode 'ret))\n",
    "            (interpret c program))])))\n",
    "\n",
    "; fetch an instruction based on the current pc\n",
    "(define (fetch c program)\n",
    "  (define pc (cpu-pc c))\n",
    "  ; the behavior is undefined if pc is out-of-bounds\n",
    "  (serval:bug-on (< pc 0))\n",
    "  (serval:bug-on (>= pc (vector-length program)))\n",
    "  ; return the instruction at program[pc]\n",
    "  (vector-ref program pc))\n",
    "\n",
    "; shortcut for getting the value of register rs\n",
    "(define (cpu-reg c rs)\n",
    "  (vector-ref (cpu-regs c) rs))\n",
    "\n",
    "; shortcut for setting register rd to value v\n",
    "(define (set-cpu-reg! c rd v)\n",
    "  (vector-set! (cpu-regs c) rd v))\n",
    "\n",
    "; execute one instruction\n",
    "(define (execute c opcode rd rs imm)\n",
    "  (define pc (cpu-pc c))\n",
    "  (case opcode\n",
    "    [(ret)  ; return\n",
    "       (set-cpu-pc! c 0)]\n",
    "    [(bnez) ; branch to imm if rs is nonzero\n",
    "       (if (! (= (cpu-reg c rs) 0))\n",
    "           (set-cpu-pc! c imm)\n",
    "           (set-cpu-pc! c (+ 1 pc)))]\n",
    "    [(sgtz) ; set rd to 1 if rs > 0, 0 otherwise\n",
    "       (set-cpu-pc! c (+ 1 pc))\n",
    "       (if (> (cpu-reg c rs) 0)\n",
    "         (set-cpu-reg! c rd 1)\n",
    "         (set-cpu-reg! c rd 0))]\n",
    "    [(sltz) ; set rd to 1 if rs < 0, 0 otherwise\n",
    "       (set-cpu-pc! c (+ 1 pc))\n",
    "       (if (< (cpu-reg c rs) 0)\n",
    "         (set-cpu-reg! c rd 1)\n",
    "         (set-cpu-reg! c rd 0))]\n",
    "    [(li)   ; load imm into rd\n",
    "       (set-cpu-pc! c (+ 1 pc))\n",
    "       (set-cpu-reg! c rd imm)]))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Application Code\n",
    "\n",
    "This is the systems code, that we need to perform the verification. This can be implemented in a high-level language such as `c` and can be compiled using the `gcc` compiler corresponding to the instruction set architecture of the system. Then from the binary, instructions should be extracted. Disassembled code is used as the implementation of the systems code for the verification process. \n",
    "\n",
    "\n",
    "### Example Application\n",
    "An example application code implementation, for the ToyRISC example instruction set is as below,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "#|\n",
    "  Sign implementation\n",
    "|#\n",
    "\n",
    "#|\n",
    "0: sltz a1, a0   ; a1 <- if (a0 < 0) then 1 else 0\n",
    "1: bnez a1, 4    ; branch to 4 if a1 is nonzero\n",
    "2: sgtz a0, a0   ; a0 <- if (a0 > 0) then 1 else 0\n",
    "3: ret           ; return\n",
    "4: li   a0, -1   ; a0 <- -1\n",
    "5: ret           ; return\n",
    "|#\n",
    "\n",
    "(define sign-implementation #(\n",
    " (sltz 1 0 #f)\n",
    " (bnez #f 1 4)\n",
    " (sgtz 0 0 #f)\n",
    " (ret #f #f #f)\n",
    " (li 0 #f -1)\n",
    " (ret #f #f #f)\n",
    "))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Specification\n",
    "\n",
    "Finally, we need to have the specification for the imeplementation where we evaluate the consistency of the implementation. We write the specification in Racket syntax with Serval-defined constructs."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example Specification\n",
    "\n",
    "The example specification for the application code is defined below. In addition to the functional specification, there are definitions related to the safety properties of the specification."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "#|\n",
    "  Sign specification\n",
    "|#\n",
    "\n",
    "; Note that we mark the struct as mutable and transparent\n",
    "; for better debugging and interoperability with Serval libraries\n",
    "(struct state (a0 a1) #:mutable #:transparent) ; specification state\n",
    "\n",
    "; functional specification for the sign code\n",
    "(define (spec-sign s)\n",
    "  (define a0 (state-a0 s))\n",
    "  (define sign (cond\n",
    "    [(positive? a0)  1]\n",
    "    [(negative? a0) -1]\n",
    "    [else            0]))\n",
    "  (define scratch (if (negative? a0) 1 0))\n",
    "  (state sign scratch))\n",
    "\n",
    "; abstraction function: impl. cpu state to spec. state\n",
    "(define (AF c)\n",
    "  (state (cpu-reg c 0) (cpu-reg c 1)))\n",
    "\n",
    "; Mutable version of sign specification\n",
    "(define (spec-sign-update s)\n",
    "  (let ([s2 (spec-sign s)])\n",
    "    (set-state-a0! s (state-a0 s2))\n",
    "    (set-state-a1! s (state-a1 s2))))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## State-machine refinement\n",
    "\n",
    "State machine refinement is the systematic process of transforming an abstract or high-level specification of a system into a more detailed and concrete representation while preserving the intended behavior and properties. It involves incrementally adding more specific details to the states, transitions, and actions of a state machine, ensuring consistency with the abstract specification and enabling stepwise development, formal analysis, and verification of complex systems.\n",
    "\n",
    "Serval asks for four specification inputs.\n",
    "  1. A definition of specification state.\n",
    "  2. A functional specification that describes the intended behavior.\n",
    "  3. An abstraction function (AF) that maps an implementation state to a specification state.\n",
    "  4. A representation invariant (RI) over an implementation state must hold before and after executing a program.\n",
    "\n",
    "\n",
    "### Example State-machine refinement\n",
    "\n",
    "State-machine refinement is evaluated symbolically. Serval defines the `serval:verify-refinement` construct to feed corresponding components such as implementation, specification, etc into the verification problem. Example state-machine refinement for the implementation is given below,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "#| State-machine refinement |#\n",
    "\n",
    "; Fresh implementation state\n",
    "(define-symbolic X Y integer?)\n",
    "(define c (cpu 0 (vector X Y)))\n",
    "\n",
    "; Fresh specification state\n",
    "(define-symbolic a0 a1 integer?)\n",
    "(define s (state a0 a1))\n",
    "\n",
    "; Counterexample handler for debugging\n",
    "(define (handle-counterexample sol)\n",
    "  (printf \"Verification failed:\\n\")\n",
    "  (printf \"Initial implementation state: ~a\\n\" (evaluate (cpu 0 (vector X Y)) sol))\n",
    "  (printf \"Initial specification state: ~a\\n\" (evaluate (state a0 a1) sol))\n",
    "  (printf \"Final implementation state ~a\\n\" (evaluate c sol))\n",
    "  (printf \"Final specification state ~a\\n\" (evaluate s sol)))\n",
    "\n",
    "; Verify refinement\n",
    "(define (verify-refinement)\n",
    "  (serval:verify-refinement\n",
    "  #:implstate c\n",
    "  #:impl (λ (c) (interpret c sign-implementation))\n",
    "  #:specstate s\n",
    "  #:spec spec-sign-update\n",
    "  #:abs AF\n",
    "  #:ri (const #t)\n",
    "  null\n",
    "  handle-counterexample))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Safety properties\n",
    "\n",
    "Safety properties in formal verification refer to specifications that assert the absence of specific undesirable behaviors or violations within a system. These properties focus on preventing or ruling out certain scenarios or errors, ensuring that the system does not reach states or exhibit behaviors that could lead to safety hazards or incorrect outcomes. By expressing safety properties using formal languages like temporal logic, formal verification techniques can rigorously analyze and verify that the system satisfies these properties, providing assurance that critical safety requirements are met and potential vulnerabilities or risks are identified and mitigated.\n",
    "\n",
    "### Example Safety property\n",
    "\n",
    "Serval defines the `serval:check-step-consistency` construct to feed state-related data, which will be used for the safety property verification. An example of safety property for the implementation is given below,\n",
    "\n",
    "Let's consider an example safety property with the functional specification of the sign program. Suppose one wants to verify that its result depends only on register `a0`, independent of the initial value in `a1`. One may use a standard noninterference property, step consistency, which asks for an unwinding relation `∼` over two specification states `s1` and `s2` as stated in the following definition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "#| Safety property |#\n",
    "\n",
    "(define (~ s1 s2)\n",
    "  (equal? (state-a0 s1) (state-a0 s2))) ; filter out a1\n",
    "\n",
    "(define (verify-safety)\n",
    "  (serval:check-step-consistency\n",
    "    #:state-init (λ () (define-symbolic* X Y integer?) (state X Y))\n",
    "    #:state-copy (λ (s) (struct-copy state s))\n",
    "    #:unwinding ~\n",
    "    spec-sign-update))\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Verification\n",
    "\n",
    "Finally, we execute the verification process by invoking the Racket unit testing constructs with state machine refinement and safety properties."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ToyRISC tests\n",
      "[ RUN      ] \"ToyRISC Refinement\"\n",
      "[       OK ] \"ToyRISC Refinement\" (96ms cpu) (806ms real) (37 terms)\n",
      "[ RUN      ] \"ToyRISC Safety\"\n",
      "[       OK ] \"ToyRISC Safety\" (28ms cpu) (694ms real) (27 terms)\n",
      "2 success(es) 0 failure(s) 0 error(s) 2 test(s) run\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<code>0</code>"
      ],
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(run-tests (test-suite+ \"ToyRISC tests\"\n",
    "  (test-case+ \"ToyRISC Refinement\" (verify-refinement))\n",
    "  (test-case+ \"ToyRISC Safety\" (verify-safety))))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's modify the implementation a bit to introduce an error to observe the behavior in a situation where implementation does not satisfy the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "(define not-sign-implementation #(\n",
    " (sltz 1 0 #f)\n",
    " (bnez #f 1 4)\n",
    " (sgtz 0 0 #f)\n",
    " (ret #f #f #f)\n",
    " (li 0 #f -2)\n",
    " (ret #f #f #f)\n",
    "))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "(define (fail-verify-refinement)\n",
    "  (serval:verify-refinement\n",
    "  #:implstate c\n",
    "  #:impl (λ (c) (interpret c not-sign-implementation))\n",
    "  #:specstate s\n",
    "  #:spec spec-sign-update\n",
    "  #:abs AF\n",
    "  #:ri (const #t)\n",
    "  null\n",
    "  handle-counterexample))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ToyRISC tests\n",
      "[ RUN      ] \"ToyRISC Refinement\"\n",
      "Failed assertions:\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "--------------------\n",
      "ToyRISC tests > ToyRISC Refinement\n",
      "FAILURE\n",
      "name:       check-unsat?\n",
      "location:   /serval/serval/lib/unittest.rkt:46:13\n",
      "params:\n",
      "  '((model\n",
      "   [X -1]\n",
      "   [a0 -1]))\n",
      "--------------------\n",
      "0 success(es) 1 failure(s) 0 error(s) 1 test(s) run\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<code>1</code>"
      ],
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(run-tests (test-suite+ \"ToyRISC tests\"\n",
    "  (test-case+ \"ToyRISC Refinement\" (fail-verify-refinement))))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, we can observe the assertion failure for the modification we did and provides a counterexample to reproduce the error.\n",
    "\n",
    "\n",
    "In conclusion, in this post, we looked at Serval verification framework with the objective of utilizing it for systems code verification. We looked at the simple example that comes with the Serval framework and executed it on Jupyter Notebook as an interactive proof. This same framework can be used for more complex verification scenarios to provide correctness guarantees for systems code."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Racket",
   "language": "racket",
   "name": "racket"
  },
  "language_info": {
   "codemirror_mode": "scheme",
   "file_extension": ".rkt",
   "mimetype": "text/x-racket",
   "name": "Racket",
   "pygments_lexer": "racket",
   "version": "8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}