Skip to main content

Tracking Non Atomic Data Types

In general, processes do not execute atomically, since the operating system may interrupt processes between essentially any two instructions, allowing other processes to run. If your application's process is not prepared for these interruptions, another process may be able to interfere with it, causing the data structures to end up in inconsistent states if arbitrary code is executed between them.

A non atomic condition is a vulnerability to interference caused by untrusted processes. These are conditions caused by processes running other, different programs, which introduce other actions between steps of the program. These other programs might be invoked by an attacker.

This use case illustrates how to use Ocular to analze for non atomic data types, using the FreeRTOS real-time operating system kernel as the example target application.

Downloading the FreeRTOS Application​

Download the FreeRTOS application and unzip the source code into the Ocular subjects directory, for example subjects/FreeRTOS.

Creating the FreeRTOS Application CPG​

importCpg("subjects/FreeRTOS")

FreeRTOS's CPG is automatically loaded into memory and your workspace.

Declaring an Array of Primitive Types​

val primitiveTypes = List("int", "float", "double", "void", "size_t", "ANY", "void", "char", "short")

Calling a Convenience Function to get LineNumber​

def getLineNumber(ln : Option[Integer]) = (ln match { case Some(x) => x ; case None => 0 }).asInstanceOf[Int]

Declaring a Data Structure of User Defined Types​

case class UDT(uType : String, uName : String,  methodName : String, fileName : String, lineNumber : Integer)

Acquiring all Identifiers into UDT Data Structure​

Negative filter on primitive types.

val udtList = cpg.identifier.l.map {
   i => UDT(i.typeFullName, i.name, i.start.method.name.l.head, i.start.file.name.l.head, getLineNumber(i.lineNumber))
} filter {
   p => !primitiveTypes.exists(e => p.uType.contains(e))
} distinct

Storing Findings in a Multimap Keyed by Identified methodName​

import collection.mutable._
val udtMap = new HashMap[String,Set[UDT]] with MultiMap[String,UDT]
udtList.foreach { 
item => udtMap.addBinding(item.methodName, item)
}

Storing Findings in a Multimap Keyed by Identified Type​

import collection.mutable._
val udtMapByType = new HashMap[String,Set[UDT]] with MultiMap[String,UDT]
udtList.foreach { 
item => udtMapByType.addBinding(item.uType, item)
}

implicit def flat[K,V](kv: (K, Option[V])) = kv._2.map(kv._1 -> _).toList

Calling a Convenience Function to get Range Given Start and End​

def getRange(start : Int , end : Int) = start to end toList

Giving functionName Return all callOuts within Scope of the Function​

def getCallOutDetails(fnName:String) = cpg.method.name(fnName).callOut.l.map(co => (co.name , getLineNumber(co.lineNumber))).sortBy(_._2)

Optimizing Name Replacement​

def getCallOutDetails(fnName:String) = cpg.method.name(fnName).callOut.l.par.map(co => (co.name , getLineNumber(co.lineNumber))).toList.sortBy(_._2)

Calling a Convenience Function for Holding Functions with CRITICAL SECTIONS with Ranges​

case class WithCriticalSection(fnName : String, fileName : String, csRange : List[(String, Int, Int)])

Specifying Functions to Optimize Ranging​

For situations in which multiple critical sections exists in a method (function).

def getBounds(dataTuples : List[(String,Int)]) =
  dataTuples.foldLeft((List.empty[(String, Int)], Option.empty[(String, Int)])) {
    case ((state, previousSignal), signal) =>
      if (previousSignal.exists(_._1.contains("EXIT")) && signal._1.contains("EXIT")) {
        (state.dropRight(1) :+ signal, Some(signal))
      } else {
        (state :+ signal, Some(signal))
      }
  }

def getRange(enterExits : (List[(String, Int)], Option[(String, Int)])) =
  enterExits._1.foldLeft(
      (List.empty[(String, Int, Int)], Option.empty[(String, Int, Int)])) {
      case ((state, accSignal), signal) =>
        if (signal._1.contains("ENTER")) {
          (state, Some(("CRITICAL_SECTION_RANGE", signal._2, 0)))
        } else {
          val enterExt = accSignal.map(elem => elem.copy(_3 = signal._2))
          (state :+ enterExt.get, Option.empty)
        }
    }._1

Getting Entire callOut Trace for Each Method that Encompasses taskENTER_CRITICAL​

val callMap = cpg.method.filter(_.callOut.name("taskENTER_CRITICAL")).l map {
  s => Map(s.name -> (s.start.file.name.head, getCallOutDetails(s.name.replaceAll("\\*",""))))
} reduce(_ ++ _)

Getting Entire callOut Trace for Each Method that DOES NOT Encompass taskENTER_CRITICAL​

val callMapWithoutCS = cpg.method.filterNot(_.callOut.name("taskENTER_CRITICAL")).l map {
          s => Map(s.name -> (s.start.file.name.headOption.getOrElse("NOT_IDENTIFIED"), getCallOutDetails(s.name.replaceAll("\\*",""))))
        } reduce(_ ++ _)

Optimizing Replacement​

def timeTaken[R](block: => R): R = {
    val t0 = System.nanoTime()
    val result = block    // call-by-name
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) + "ns")
    result
}

val mWithoutCS = cpg.method.filterNot(_.callOut.name("taskENTER_CRITICAL")).l

timeTaken {
   val callMapWithoutCS = mWithoutCS.map {
         s => Map(s.name -> (s.start.file.name.headOption.getOrElse("NOT_IDENTIFIED"),  getCallOutDetails(s.name.replaceAll("\\*",""))))
   } reduce(_ ++ _)
}

Filtering callMap and Fitting into WithCriticalSection​

val callMapFiltered = callMap map {
    case(k,v) => k -> (v._1 , getRange(getBounds(v._2.filter(t => t._1.contains("taskENTER_CRITICAL") || t._1.contains("taskEXIT_CRITICAL")))))
} map { case(k,v) => k -> WithCriticalSection(k,v._1,v._2) }

For example called xQueueAddToSet. Pick any type from udtMapByType say for instance tfp_format.

…
"SIZEOF_LONG_LONG" -> Set(
    UDT("SIZEOF_LONG_LONG", "lng", "tfp_format", "../../Downloads/dahling-fw/Src/utils/tinystdio.c", 398),
    UDT("SIZEOF_LONG_LONG", "lng", "tfp_format", "../../Downloads/dahling-fw/Src/utils/tinystdio.c", 412),
    UDT("SIZEOF_LONG_LONG", "lng", "tfp_format", "../../Downloads/dahling-fw/Src/utils/tinystdio.c", 408)
  
...

val nonAtomicUsedInCS =callMap.getOrElse("tfp_format","NOT_FOUND")
val nonAtomicUsedInNoCS =callMapWithoutCS.getOrElse("tfp_format","NOT_FOUND")

If (nonAtomicUsedInCS.size > 0 && nonAtomicUsedInNoCS.size > 0), this implies that a non atomic data type is used both in guarded context and not in guarded context, possibly leading to deadlock or starvation.

Determining the Location Details of Where the Non Atomic Data type is Used​

val udtSet = udtMap("xStreamBufferReset")
val callSiteData = callMapFiltered.get("xStreamBufferReset").get

udtSet.foreach {
  udt => callSiteData.csRange.map { item => 
    if((udt.lineNumber > item._2) && (udt.lineNumber < item._3)) {
      printf("[%s] is bound in critical section at [%d] between [%d] and [%d] in methodName [%s] located at [%s]\n", udt.uName, udt.lineNumber, item._2, item._3, udt.methodName, udt.fileName)
    }
  }
}