Concolic Execution Rules JS Builtins

JavaScript built-in functions are implemented by the JavaScript engine itself, in C++ or Assembly language. We need to create custom rules (model) for these functions due to the following reasons: 1/ our taint mechanism alters the types and values of primitives (by wrapping them in a special object). Passing these tainted primitives directly to the built-in functions can raise exceptions. 2/ we need to ensure that the taint information is propagated to the return values of built-in functions to reflect changes in taint status.

However, not all the builtins are need to be modeled. In our context, a taint value indicates that it can either be clobbered by an attacker (e.g., DOM Nodes or objects loaded from the document such as document.cookie) or is derived from a value that can be clobbered. The typical taint flow directions are: 1/ From the object to primitive values (through property lookups) and 2/ primitive values (mostly String) to other primitive values. Therefore, we focus on the string-related builtins.

For the built-in functions, we treat them at three levels: fully modeled, non-affected, and concretized. For fully modeled functions, we execute the original function with stripped taint information and then re-taint the return value with customized taint handling (update and merge). Non-affected taint means that we execute the original function without stripping the taint information of the arguments. This type of modeling usually applies to functions like array.push that can take object types as argument types and do not require updating the taint information. Concretize means that we execute the original function with stripped taint information of the arguments. Usually, the arguments of these functions are not likely to be tainted, or we don't want to taint its return value anyway, or the function is not supported currently. The built-in functions in first two types of modeling are taint-aware, while the last type is taint-oblivious.

We prioritize modeling built-in functions whose return values are strings or contain strings. For example, String.prototype.concat and String.prototype.replace are modeled because they return strings. We also model String.prototype.match and String.prototype.matchAll because they return objects that contain strings.

Modeled Builtins

Currently, [x] means that function has been modeled either fully or non-affected, [-] means that the function has been modeled in concretized level intentionally.

• String

  • charCodeAt: 44,240,216
  • charAt: 740,467
  • indexOf: 585,641
  • replace: 564,660
  • toLowerCase: 418,743
  • split: 384,974
  • substring: 246,505
  • fromCharCode: 243,656
  • concat: 226,049
  • slice: 220,930
  • match: 193,496
  • startsWith: 84,950
  • toUpperCase: 70,408
  • trim: 67,697
  • substr: 60,263
  • replaceAll: 24,276
  • includes: 21,396
  • lastIndexOf: 17,663
  • toString: 17,287
  • endsWith: 14,469
  • search: 4,173
  • localeCompare: 3,146
  • toLocaleUpperCase: 1,420
  • repeat: 1,058
  • toLocaleLowerCase: 966
  • valueOf: 948
  • padStart: 489
  • trimStart: 384
  • matchAll: 102

• Array

  • [-] isArray: 2,593,943
  • push: 2,415,247
  • forEach: 574,487
  • pop: 559,068
  • [-] indexOf: 370,365
  • concat: 246,614
  • filter: 237,906
  • slice: 210,745
  • join: 205,666
  • map: 138,344
  • shift: 94,455
  • unshift: 75,859
  • reduce: 60,089
  • [-] some: 50,328
  • sort: 49,217
  • [-] includes: 41,055
  • splice: 24,428
  • from: 18,694
  • every: 13,805
  • [-] find: 7,471
  • reverse: 5,442
  • [-] lastIndexOf: 3,300
  • fill: 2,607
  • values: 1,795
  • flatMap: 312
  • findIndex: 300
  • [-] at: 254
  • reduceRight: 190
  • keys: 173

• JSON

  • parse: 14,559
  • stringify: 13,641

• RegExp

  • test: 349,429
  • exec: 190,636

• Object

  • hasOwnProperty: 3,316,177
  • keys: 449,704
  • defineProperty: 365,849
  • getOwnPropertySymbols: 203,084
  • getOwnPropertyDescriptor: 78,373
  • getOwnPropertyDescriptors: 67,238
  • defineProperties: 67,000
  • entries: 57,520
  • create: 56,917
  • assign: 56,094
  • getPrototypeOf: 42,305
  • fromEntries: 40,050
  • construct: 31,654
  • get: 18,236
  • freeze: 12,963
  • isFrozen: 11,473
  • setPrototypeOf: 11,465
  • getOwnPropertyNames: 10,860
  • isArray: 3,880
  • values: 3,871
  • escape: 3,658
  • Promise: 2,407
  • toString: 2,398
  • has: 1,368
  • isPrototypeOf: 1,082
  • isExtensible: 375
  • log: 360
  • error: 159
  • set: 142

• Function

  • apply: 506,956
  • call: 308,640
  • bind: 12,534

• Number

  • toString: 264,038
  • isNaN: 11,558
  • toFixed: 7,768
  • isFinite: 5,916
  • isInteger: 307
  • isSafeInteger: 142

• Math

  • floor: 677,331
  • sqrt: 465,372
  • sin: 285,918
  • cos: 222,679
  • random: 133,396
  • round: 100,014
  • max: 98,279
  • abs: 77,884
  • min: 61,063
  • atan2: 51,330
  • asin: 25,402
  • acos: 17,976
  • pow: 9,083
  • trunc: 5,129
  • sign: 3,896

• Set

  • has: 314,145
  • add: 138,727
  • forEach: 11,278
  • delete: 2,666
  • clear: 1,379
  • values: 463

• Map

  • get: 245,574
  • set: 135,773
  • has: 31,473
  • forEach: 27,046
  • delete: 19,139
  • keys: 1,517
  • entries: 954
  • clear: 924
  • values: 298

• WeakMap

  • get: 76,237
  • set: 23,825
  • has: 19,670
  • delete: 239

• WeakSet

  • has: 3,658
  • add: 1,281
  • delete: 109