Ideas for simplified or assisted rule creation

[stevenengland]

Hi community,

has there ever been an attempt to simplify the rule creation (bring your own lints ;)) or even assist this process? Like

• a meta model that allows rules to be expressed by YAML instead of go?
• pre trained LLMs as a natural language to code bridge?

Does that sound at all desirable or useful to someone?

TLDR;
I am student currently taking the course cryptography. Starting in about 6 month there will be kind of a project that I do some preliminary research for. It will be a more practical project. And I stumbled across this linter project. I asked myself, how easy or not it is for people to write down their own rule and if there might be some gap between analysts and devs that could be bridged somehow. See above ;) Maybe this is all obsolete because if all users of this tool are working in a CA then there might be enough people that are able to write rules, aren't there? But if it there is any need for this I could imagine to engage with this topic.

Made this an issue like proposed in #932

[christopher-henderson]

Thank you @stevenengland!

This is near to my heart. My graduate research was in declarative programming languages. Specifically, I forked the Go compiler and injected my own syntax which provided a runtime for running backtracking algorithms (similar to Prolog). And, of course, my secondary focus was in cryptography.

A Bit on Declarative Programming

The attraction to declarative programming is that the user (the programmer) declares what needs to be done - not how.

Let us consider a classic Prolog program

% Facts
parent(john, mary).
parent(john, mike).
parent(mary, susan).
parent(mary, tom).
parent(mike, ann).

grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

% ?- grandparent(john, X).

We have made clear the fact that John is the parent of Mary and Mike. That Mary is the parent of Susan and Tom. And that Mike is the parent of Ann.

We have also declared a rule that states that X is a grandparent of Y if there exists some Z such that X is the parent of Z and Z is the parent of Y.

Great! A candidate algorithm to solve this problem is, of course, backtracking. However, backtracking is fiddly and takes quite a bit of book keeping. Thankfully, the Prolog runtime supplies this algorithm to us, free of charge.

All we have to do is declare the facts, the runtime will take care of the rest.

Back to ZLint

Declarative programming seems attractive for a linter. We know what we want quite well (litigious interpretations of RFCs aside)!

The problem, as I see it, comes in that it would seem impractical to conceive of a runtime that could universally solve the how of a particular lint.

Perhaps the best example of this within the ZLint codebase is lint_rsa_fermat_factorization.go. This lint executes Fermat's factorization method on a certificate's public key in order to smoke check its susceptibility to such an attack.

Let us consider what this might look like if ZLint offered a declarative interface for ZLint construction. Specifically, let us first address the issue of the inputs to the lint.

Declarativelty Identifying the Inputs to a Lint

Shuffling the certificate to the top level of the lint is easy enough. However, in order to run this factorization lint, what you really need in is the certificate's public key. Specifically, casted to an RSA key and extract it's N.

c.PublicKey.(*rsa.PublicKey).N

Perhaps the YAML for this statement might look like the following (I have not put great thought into this YAML).

name: fermat_factorization
input:
  field:
    name: PublicKey
    cast: rsa.PublicKey
    follow:
      name: 'N'

I am sure that there is an elegant, recursive, YAML structure that could accurately the describe what we are attempting here. However, I am not sure that it would be a better experience than simply saying c.PublicKey.(*rsa.PublicKey).N.

This issue only gets more pernicious once we hit the handful of lints which need to inspect the raw binary encoding of a given certificate. Although I do not have a list readily available, I can tell you that there are more than a few lints that have to perform ad-hoc inspections on these certificate.

The Lint Itself

We have identified that we first need to be able to declaratively extract the precise input into the lint. The next question is, how do we declaratively define the lint itself?.

That is, much like Prolog, we need to define a goal. This is not so bad when the goal is a simple relationship. Something equality, ordinality, contains relationships, and so on.

name: fermat_factorization
input:
  ...
lint:
	(eq | contains | gt | lt | exists | etc ): <Value>

But what about lint_rsa_fermat_factorization? Specifically, the workhorse function checkPrimeFactorsTooClose? Surely there is no generic runtime that can just solve this for you. At the end of the day, this Go function needs to be written and referred to.

name: fermat_factorization
input:
  ...
lint:
	func: checkPrimeFactorsTooClose

Perhaps such a structure would dynamically pull up a checkPrimeFactorsTooClose function that has been embedded in the runtime executes that. However, this function would still need to be written by the ZLint contributor. The only difference is, instead of writing the function to work intimately with the intent of the given lint, the function must be written as part of a runtime framework and then referred to declaratively.

Final Thoughts

• Would this be a better experience? I doubt it.
• Is this something that ZLint itself would implement? Almost certainly not.
• Should you fork ZLint and continue on with your research? I encourage it!

ZLint implements a visitor pattern which has done well for ZLint (and other linters) for quite a few years. Additionally, ZLint does not have any full time contributors. ZLint is purely a side project for everyone involved. I am the Code Czar that keeps the repo humming and there are a handful more contributors from CAs that come in to implement lints as they discover internal issues. I do not believe that any of the typical contributors would have an appetite for what is, essentially, a rewrite of a tool that has been battle tested in production for over half a decade. It works well, as-is, and we all have larger fish to fry in our lives and primary duties.

But do not let this deter you! Enjoy your time in academia. This project may not yield practical results, but you are not constrained by "practical" results! This is your opportunity to explore the world of computing without the shackles of business (or life) constraints.

[stevenengland]

Hi Christopher,

what an amazing answer. Thank you so much. I really mean that. Full of information, very illustrative and very motivating although you proof it might not be of much practical value what I was trying to achieve. I'll need some time to think through all this.

Again: Thanks a lot. One can see how much effort you put in all your explainations :-)