Concolic Execution Rules
A rule is a function that manages the symbolic information associated with the arguments and results of various operations (e.g., function calls, binary operations, etc.). These rules can introduce, update, or delete symbolic information based on the given contextual conditions.
During the runtime hook of each operation, the appropriate rule is selected based on the context (e.g., operator, function name, argumen types) to manage the symbolic field, while simultaneously applying the original function or operation to update the concrete field.
Each rule are building from three components: the original built-in function or operator name, the condition check function, and the model function. The condition check function evaluates whether the model function should be applied based on the current context (e.g., the type of arguments). If the condition check function returns true, the model function is then applied.
For example, when String.fromCharCode is invoked, the TaintPropRules.fromCharCodeTaintPropRule is selected to handle the built-in function. First, we concretize all the arguments of the function call and invoke the built-in String.fromCharCode function with them to get the concrete results. Then, the condition function of String.fromCharCode checks all its arguments to see if any of them are wrapped values. If the condition returns true, the model function of String.fromCharCode is applied to wrap the result with a new wrapped value, update the symbolic expression, and record that String.fromCharCode has been applied.
In addition to handling built-in method calls, we also need to create rules for property setting operations. Setting a property on a specific type of object can trigger cross-boundary dataflows. For example, document.getElementById("greeting").innerText = userInput; should not directly set the wrapped value to the .innerText property of a DOM element. We must handle such operations with appropriate rules to ensure proper taint propagation and avoid raising any error.
I collected a list of most frequently used built-in APIs for the Web by crawling the top 500 websites and logging their built-in function invocations (through the defined task: count-most-frequently-used-apis-builtins).
-
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
-
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
- parse: 14,559
- stringify: 13,641
- 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
-
RegExp
- test: 349,429
- exec: 190,636
-
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
-
HTMLDocument
- createElement: 74,289
- createTextNode: 14,509
- createElementNS: 13,631
- querySelectorAll: 11,758
- createDocumentFragment: 10,529
- getElementsByTagName: 6,594
- getElementById: 6,068
- addEventListener: 5,421
- querySelector: 5,420
- dispatchEvent: 2,214
- getElementsByClassName: 1,636
- hasOwnProperty: 1,524
- elementFromPoint: 1,304
- removeEventListener: 497
- createRange: 473
- createTreeWalker: 409
- contains: 324
- createComment: 299
- createEvent: 229
- getElementsByName: 184
- getRootNode: 135
- compareDocumentPosition: 102
-
HTMLAnchorElement
- setAttribute: 42,042
- getAttribute: 23,525
- addEventListener: 16,454
- appendChild: 7,350
- hasAttribute: 3,834
- removeAttribute: 2,482
- matches: 1,408
- removeChild: 1,359
- insertBefore: 1,318
- compareDocumentPosition: 1,040
- getBoundingClientRect: 802
- getElementsByTagName: 624
- querySelectorAll: 522
- hasOwnProperty: 364
- cloneNode: 332
- querySelector: 326
- removeEventListener: 256
- getClientRects: 212
- getRootNode: 138
-
HTMLDivElement
- appendChild: 27,599
- setAttribute: 27,204
- addEventListener: 23,802
- getAttribute: 18,559
- matches: 8,145
- querySelector: 7,924
- hasAttribute: 7,288
- querySelectorAll: 4,866
- getElementsByClassName: 4,452
- getElementsByTagName: 4,065
- closest: 3,258
- getBoundingClientRect: 3,059
- removeAttribute: 2,977
- removeChild: 2,928
- insertBefore: 2,593
- compareDocumentPosition: 2,373
- append: 1,910
- removeEventListener: 1,150
- cloneNode: 1,119
- hasOwnProperty: 744
- getRootNode: 203
- dispatchEvent: 182
- insertAdjacentElement: 106
- getAttributeNames: 104
-
HTMLSpanElement
- setAttribute: 19,096
- appendChild: 10,290
- getAttribute: 1,732
- hasAttribute: 1,570
- matches: 1,496
- querySelector: 1,480
- addEventListener: 684
- hasOwnProperty: 462
- removeAttribute: 447
- getBoundingClientRect: 354
- getElementsByTagName: 278
- setAttributeNS: 240
- removeChild: 206
- hasAttributes: 200
- querySelectorAll: 162
- insertBefore: 158
- contains: 144
- cloneNode: 130
- remove: 101
- replaceChild: 100
-
HTMLScriptElement
- getAttribute: 67,901
- matches: 7,852
- querySelector: 7,490
- setAttribute: 3,226
- addEventListener: 1,008
- hasAttribute: 993
- querySelectorAll: 578
- removeEventListener: 556
- getBoundingClientRect: 160
- isEqualNode: 145
-
HTMLLinkElement
- getAttribute: 33,161
- setAttribute: 3,638
- isEqualNode: 904
- hasAttribute: 160
- addEventListener: 158
-
HTMLCanvasElement
- matches: 366
- querySelector: 366
- getContext: 281
-
HTMLButtonElement
- setAttribute: 3,543
- addEventListener: 2,393
- getAttribute: 1,618
- compareDocumentPosition: 876
- appendChild: 757
- removeAttribute: 340
- hasAttribute: 279
- getElementsByTagName: 130
- removeEventListener: 122
- hasOwnProperty: 116
- matches: 112
-
HTMLLIElement
- setAttribute: 9,906
- querySelector: 4,028
- appendChild: 3,604
- matches: 3,406
- getAttribute: 3,116
- addEventListener: 2,546
- getElementsByTagName: 1,604
- hasAttribute: 1,178
- insertBefore: 566
- getElementsByClassName: 532
- querySelectorAll: 516
- hasOwnProperty: 360
- setAttributeNS: 320
- removeEventListener: 294
- removeChild: 190
- cloneNode: 116
-
HTMLMetaElement
- getAttribute: 8,175
- isEqualNode: 2,719
- setAttribute: 1,076
- hasAttribute: 328
-
HTMLUListElement
- appendChild: 3,201
- setAttribute: 2,005
- insertBefore: 1,926
- getAttribute: 446
- hasAttribute: 446
- addEventListener: 442
- removeChild: 370
- querySelectorAll: 294
- getElementsByClassName: 157
-
HTMLTableRowElement
- insertCell: 1,146
- appendChild: 212
-
HTMLIFrameElement
- setAttribute: 575
- getAttribute: 313
-
HTMLTableCellElement
- appendChild: 216
-
HTMLFormElement
- getAttribute: 165
- setAttribute: 125
- hasAttribute: 116
-
HTMLSourceElement
- setAttribute: 668
- addEventListener: 320
- removeAttribute: 160
-
HTMLVideoElement
- addEventListener: 530
- setAttribute: 200
- canPlayType: 192
-
HTMLBodyElement
- appendChild: 1,383
- getAttribute: 1,380
- addEventListener: 1,308
- matches: 904
- querySelector: 832
- hasAttribute: 638
- contains: 506
- removeChild: 473
- setAttribute: 306
- replaceChild: 222
- compareDocumentPosition: 218
- insertBefore: 136
-
HTMLHtmlElement
- getAttribute: 2,409
- contains: 1,846
- addEventListener: 602
- hasAttribute: 412
- removeChild: 395
- appendChild: 390
- compareDocumentPosition: 266
-
HTMLLabelElement
- setAttribute: 184
-
HTMLSlotElement
- getAttribute: 1,196
- dispatchEvent: 284
-
HTMLInputElement
- setAttribute: 1,711
- addEventListener: 648
- closest: 608
- getAttribute: 487
-
HTMLFieldSetElement
- querySelectorAll: 804
- appendChild: 248
- getAttribute: 118
-
HTMLSelectElement
- removeChild: 494
- appendChild: 373
- addEventListener: 118
-
HTMLTableSectionElement
- insertRow: 226
-
HTMLModElement
- getAttribute: 2,156
- setAttribute: 102
-
HTMLTimeElement
- setAttribute: 976
- remove: 400
- appendChild: 160
-
HTMLPictureElement
- appendChild: 502
- setAttribute: 270
-
HTMLParagraphElement
- setAttribute: 624
- appendChild: 378
- hasOwnProperty: 112
- hasAttribute: 106
-
HTMLUnknownElement
- getAttribute: 184
-
HTMLHeadingElement
- setAttribute: 483
- appendChild: 329
- hasAttribute: 252
- getAttribute: 164
- addEventListener: 116
-
HTMLImageElement
- setAttribute: 13,185
- getAttribute: 10,481
- addEventListener: 6,224
- getBoundingClientRect: 4,502
- hasAttribute: 1,112
- removeAttribute: 826
- querySelectorAll: 424
- removeEventListener: 294
- getElementsByTagName: 256
-
Window
- parseInt: 316,087
- isNaN: 74,252
- isFinite: 41,046
- setTimeout: 30,449
- parseFloat: 20,371
- Promise: 15,916
- URL: 12,739
- URLSearchParams: 10,501
- addEventListener: 9,046
- requestAnimationFrame: 8,449
- Proxy: 6,030
- now: 5,460
- clearTimeout: 4,920
- CustomEvent: 4,565
- atob: 2,872
- structuredClone: 2,670
- unescape: 2,575
- Error: 2,383
- removeEventListener: 2,291
- Symbol: 2,186
- matchMedia: 1,572
- queueMicrotask: 1,412
- Function: 1,404
- XMLHttpRequest: 1,148
- fetch: 488
- imul: 456
- dispatchEvent: 380
- encodeURI: 374
- AbortController: 350
- clearInterval: 324
- escape: 295
- btoa: 295
- requestIdleCallback: 200
- postMessage: 161
- DOMParser: 158
- BigInt: 158
- seal: 144
- ResizeObserver: 143
- DataView: 140
- MessageChannel: 119
- cancelIdleCallback: 112
- TextDecoder: 108
-
DocumentFragment
- appendChild: 5,929
- querySelector: 1,064
- cloneNode: 728
- removeChild: 266
- querySelectorAll: 248
-
Text
- splitText: 1,640
- remove: 328
-
SVGSVGElement
- setAttribute: 11,815
- appendChild: 3,816
- getAttribute: 986
- hasAttribute: 816
- matches: 424
- hasOwnProperty: 302
- addEventListener: 194
- querySelectorAll: 156
-
SVGPathElement
- setAttribute: 14,207
- addEventListener: 650
- appendChild: 510
- hasOwnProperty: 352
- getAttribute: 149
-
SVGGElement
- appendChild: 5,943
- setAttribute: 1,811
- addEventListener: 132
-
TreeWalker
- nextNode: 74,765
-
Performance
- now: 72,405
- getEntriesByType: 1,340
- mark: 924
- getEntriesByName: 619
- measure: 306
-
CSSStyleDeclaration
- getPropertyValue: 20,314
- setProperty: 3,054
- removeProperty: 357
-
NodeList
- forEach: 34,934
-
Storage
- getItem: 6,405
- setItem: 2,448
- removeItem: 864
- key: 204
-
CustomElementRegistry
- get: 15,024
- define: 246
-
PerformanceObserver
- observe: 625
-
MutationObserver
- observe: 753
- disconnect: 251
-
IntersectionObserver
- observe: 3,488
- unobserve: 671
- disconnect: 195
-
XMLHttpRequest
- setRequestHeader: 1,068
- open: 724
- send: 723
- getAllResponseHeaders: 169
-
Crypto
- getRandomValues: 1,718
-
MediaQueryList
- addEventListener: 539
- addListener: 207
- removeEventListener: 142
-
PerformanceObserverEntryList
- getEntries: 1,527
-
WebGLRenderingContext
- getParameter: 688
- getShaderPrecisionFormat: 168
- getExtension: 130
-
WebGL2RenderingContext
- getParameter: 564
- getActiveUniform: 184
- getUniformLocation: 184
- bindBuffer: 108
-
SVGAnimateElement
- setAttribute: 14,416
-
SVGAnimateTransformElement
- setAttribute: 10,374
-
SVGAnimateMotionElement
- setAttribute: 8,064
-
SVGCircleElement
- hasAttribute: 1,532
- setAttribute: 650
-
SVGStopElement
- addEventListener: 576
-
SVGClipPathElement
- addEventListener: 132
-
SVGRectElement
- addEventListener: 132
-
SVGDefsElement
- addEventListener: 150
-
SVGUseElement
- setAttribute: 905
- getAttribute: 412
- matches: 338
- setAttributeNS: 301
- hasOwnProperty: 182
-
CanvasRenderingContext2D
- fillRect: 42,978
- strokeRect: 5,476
- lineTo: 4,704
- measureText: 524
- save: 390
- restore: 390
- fillText: 272
- setTransform: 256
- Related Works
- HTML Injection
- DOM Clobbering
- Evaluation
- Discussion
- Others