Sitelet https://web.archive.org/web/20251231130433/https://github.com/github/codeql/pull/7785
Skip to content

Restrict AST nodes according to string length #7785

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
Z80coder merged 7 commits into from
Feb 4, 2022
Merged

Restrict AST nodes according to string length #7785

Z80coder merged 7 commits into from
Feb 4, 2022

Conversation

@Z80coder
Copy link
Contributor

@Z80coder Z80coder commented Jan 28, 2022 •
edited
Loading

Fix for the catastrophic error identified in https://github.com/github/ml-ql-adaptive-threat-modeling/issues/1618

The catastrophic error is CatastrophicError "String too long (5395415 characters)", which occurs when we tokenize the string associated with the ASTNode. I've added a restriction to throw away strings that are longer than 1,000,000 characters before we attempt to tokenize them.

@github-actions github-actions bot added the JS label Jan 28, 2022
@Z80coder Z80coder requested a review from henrymercer January 28, 2022 15:12
henrymercer
henrymercer reviewed Jan 28, 2022
View reviewed changes
Copy link
Contributor

@henrymercer henrymercer left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Have you verified that the extraction query now works on the relevant database? When we concatenate the body tokens from each AST node together to form the full body token feature, we could still potentially reach the length limit.

From a brief dive into the code, the string limit may be 1,048,576 bytes. Therefore a safer limit might be 1,048,576/(max num ast nodes in body feature) = 1,048,576/1024 = 1,024 bytes / characters. We'd need to subtract one from that for the space separator, so perhaps a 1000 character limit is sensible? I think it probably still needs testing though.

@Z80coder
Copy link
Contributor Author

Z80coder commented Jan 31, 2022

Sorry this is a draft, and I shouldn't have asked you to take a look yet.

No this does not solve the problem at all.

The difficulty, seems to be, that the size restriction in getBodyTokenFeature, which is currently 256, isn't strict enough. Lowering that to, say, 32, avoids this problem.

Perhaps I need to implement a separate predicate that somehow counts the total number of characters in all the ASTNodes of a Function and then chooses the node restriction appropriately?

@Z80coder Z80coder marked this pull request as ready for review January 31, 2022 12:29
@Z80coder Z80coder requested a review from a team as a code owner January 31, 2022 12:29
@Z80coder Z80coder requested a review from henrymercer January 31, 2022 12:29
@Z80coder
Copy link
Contributor Author

Z80coder commented Jan 31, 2022

@henrymercer I've tested that this change now fixes the problem. However, it may have other knock-ons that I don't understand. Ready for review now.

henrymercer
henrymercer reviewed Feb 1, 2022
View reviewed changes
...ntal/adaptivethreatmodeling/lib/experimental/adaptivethreatmodeling/FunctionBodyFeatures.qll Outdated
Comment on lines 149 to 152
// Performance optimization: If a function has more than getMaxChars() characters in its body subtokens,
// then featurize it as absent.
function = getFeaturizableFunction(function) and
result = strictconcat(Location l, string token |
Copy link
Contributor

@henrymercer henrymercer Feb 1, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This changes the behaviour of the function body features potentially quite considerably. The AST node limit was a factor that noticeably affected end-to-end performance, and using a different restriction here could have important implications on the runtime of the ML-powered queries.

We need to validate the runtime implications of this change before we merge it. Furthermore, we should either (a) stick with the removal of the AST node limit, train a new model on the new features and run an end-to-end evaluation, or (b) reintrodue the AST node limit, so the feature values should not change considerably.

Copy link
Contributor Author

@Z80coder Z80coder Feb 3, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

  • Will reinstate the AST node limit
  • Will collect timing measures
  • Will run end-to-end evaluation

@Z80coder

This comment was marked as outdated.

Sign in to view
@Z80coder
Copy link
Contributor Author

Z80coder commented Feb 4, 2022

End-to-end results are here:
https://github.com/github/ml-ql-adaptive-threat-modeling-backend/pull/1185
(this time against a properly worsened comparison branch). Summary:

  • nop for sqlinjection, nosqlinjection and xss
  • pathinjection has an increase in the number of results that can be recovered (compared to main), which has the knock-on that recall drops by about 8.58% (and other metrics similarly affected).

This PR should have 2 effects:

  • catastrophic failures on some databases should no longer occur
  • some enclosingFunctionBody feature values will be the empty string (rather than a very long string).

More detective work is needed to understand the cause of the increase in recoverable alerts in the end-to-end metrics.

@Z80coder
Copy link
Contributor Author

Z80coder commented Feb 4, 2022

Some timing tests. Conclusion: this change probably has no effect on query execution time.

N.B. Before each run I brutally cleared database caches and pre-compiled the queries.

repo With change Without change
willwillis_Crypto-Sentiment-Clusters_8830868/ 49.026s 49.610s
atm-query-suite-owasp-juice-shop 1m13.680s 1m12.604s
A2Z-F15 17m27.202s 17m28.127s

@Z80coder
Copy link
Contributor Author

Z80coder commented Feb 4, 2022

More detective work is needed to understand the cause of the increase in recoverable alerts in the end-to-end metrics.

The difference is due to an improvement in modeling unrelated to this PR. See https://github.com/github/ml-ql-adaptive-threat-modeling-backend/pull/1185

@Z80coder
Copy link
Contributor Author

Z80coder commented Feb 4, 2022

@henrymercer I've reinstated the AST node limit, collect timing measures (no effect) and performed end-to-end evaluation (no effect).

@Z80coder Z80coder requested a review from henrymercer February 4, 2022 14:53
henrymercer
henrymercer reviewed Feb 4, 2022
View reviewed changes
Copy link
Contributor

@henrymercer henrymercer left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks, this looks good overall. Minor suggestions to improve the code, then let's get this in.

Z80coder and others added 2 commits February 4, 2022 15:21
@Z80coder
add QL comment; inline a predicate; restore a comment
b38335a
@Z80coder @henrymercer
Update javascript/ql/experimental/adaptivethreatmodeling/lib/experime…
e57a0e0 
…ntal/adaptivethreatmodeling/FunctionBodyFeatures.qll

Co-authored-by: Henry Mercer <henrymercer@github.com>
@Z80coder Z80coder requested a review from henrymercer February 4, 2022 15:22
@Z80coder @henrymercer
Update javascript/ql/experimental/adaptivethreatmodeling/lib/experime…
be5e8da 
…ntal/adaptivethreatmodeling/FunctionBodyFeatures.qll

Co-authored-by: Henry Mercer <henrymercer@github.com>
@Z80coder Z80coder merged commit 6c3daf4 into main Feb 4, 2022
@Z80coder Z80coder deleted the z80coder/impose-length-restriction branch February 4, 2022 16:35
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@henrymercer henrymercer henrymercer approved these changes

Assignees

No one assigned

Labels

JS

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@Z80coder @henrymercer