Mailing List Archive: SPF: Devel

Grammar Requires Backtracking

Index | Next | Previous | View Threaded

william at 25thandClement

Apr 17, 2010, 12:50 PM

Post #1 of 5 (2558 views)
Permalink

Grammar Requires Backtracking

Is anyone else bothered by the fact that the grammar requires backtracking?
Specifically, because a domain-spec can include forward slashes, and because
some of the terms allow cidr masks after a domain-spec, you have to support
backtracking.

Frankly I'm not sure I want to bother supporting this. I use Ragel to parse
the policies, which is a pure regular langage parser generator. I could use
Ragel's scanner feature, or just hack the support, but as a general rule I
don't like backtracking grammars for untrusted input.

Perhaps it would have been wise to have included a %-encoded forward-slash,
as was done for spaces.

Anybody open to such an amendment?

My asynchronous spf.c library passes 90% of the 2009.10 OpenSPF test suite
(I can't yet simulate timeouts to pass the TempError tests). Many, many
thanks to those who put in the time and effort to write those test
specifications.

I gratuitously wrote an RFC 1035 master file parser and composer in C (w/
Ragel), and am of course parsing the YAML tests from C (w/ libyaml). So if
anybody was waiting for the ability to generate zone files from the test
suite, it's all but done--rfc4408-tests.c in my regress/ directory already
spits out the zones files, the code would just need to be tweaked to output
them in a more useful manner than as part of the debug output for failed
tests.

-------------------------------------------
Sender Policy Framework: http://www.openspf.org [http://www.openspf.org]
Modify Your Subscription: http://www.listbox.com/member/ [http://www.listbox.com/member/]

Archives: https://www.listbox.com/member/archive/1007/=now
RSS Feed: https://www.listbox.com/member/archive/rss/1007/
Powered by Listbox: http://www.listbox.com

vesely at tana

Apr 18, 2010, 7:26 AM

Post #2 of 5 (2454 views)
Permalink

Re: Grammar Requires Backtracking [In reply to]

On 17/Apr/10 21:50, William Ahern wrote:
> Is anyone else bothered by the fact that the grammar requires backtracking?
> Specifically, because a domain-spec can include forward slashes, and because
> some of the terms allow cidr masks after a domain-spec, you have to support
> backtracking.
>
> Frankly I'm not sure I want to bother supporting this. I use Ragel to parse
> the policies, which is a pure regular langage parser generator. I could use
> Ragel's scanner feature, or just hack the support, but as a general rule I
> don't like backtracking grammars for untrusted input.
>
> Perhaps it would have been wise to have included a %-encoded forward-slash,
> as was done for spaces.
>
> Anybody open to such an amendment?

A rewriting of the spec has been due since a couple of years ago.
Until we start that, we can presumably use
http://www.openspf.org/Community/SPFv3 to annotate various issues
(even if we won't eventually bump the version number.)

I've added a skeletal page in
http://www.openspf.org/Community/SPFv3-Grammar . Please feel free to
amend/complete it as appropriate.

> I gratuitously wrote an RFC 1035 master file parser and composer in C (w/
> Ragel), and am of course parsing the YAML tests from C (w/ libyaml). So if
> anybody was waiting for the ability to generate zone files from the test
> suite, it's all but done--rfc4408-tests.c in my regress/ directory already
> spits out the zones files, the code would just need to be tweaked to output
> them in a more useful manner than as part of the debug output for failed
> tests.

How would that work for running the test suite, given that you need
different zones --with conflicting names-- for different tests?

-------------------------------------------
Sender Policy Framework: http://www.openspf.org [http://www.openspf.org]
Modify Your Subscription: http://www.listbox.com/member/ [http://www.listbox.com/member/]

Archives: https://www.listbox.com/member/archive/1007/=now
RSS Feed: https://www.listbox.com/member/archive/rss/1007/
Powered by Listbox: http://www.listbox.com

william at 25thandClement

Apr 18, 2010, 11:01 AM

Post #3 of 5 (2452 views)
Permalink

Re: Grammar Requires Backtracking [In reply to]

On Sun, Apr 18, 2010 at 04:26:35PM +0200, Alessandro Vesely wrote:
<snip>
> >I gratuitously wrote an RFC 1035 master file parser and composer in C (w/
> >Ragel), and am of course parsing the YAML tests from C (w/ libyaml). So if
> >anybody was waiting for the ability to generate zone files from the test
> >suite, it's all but done--rfc4408-tests.c in my regress/ directory already
> >spits out the zones files, the code would just need to be tweaked to output
> >them in a more useful manner than as part of the debug output for failed
> >tests.
>
> How would that work for running the test suite, given that you need
> different zones --with conflicting names-- for different tests?

it wouldn't directly. but there are only 15 groups of tests, so it might be
useful for implementations forced to run the test suite the hard way, by
reloading zone data into BIND or NSD between test groups.

-------------------------------------------
Sender Policy Framework: http://www.openspf.org [http://www.openspf.org]
Modify Your Subscription: http://www.listbox.com/member/ [http://www.listbox.com/member/]

Archives: https://www.listbox.com/member/archive/1007/=now
RSS Feed: https://www.listbox.com/member/archive/rss/1007/
Powered by Listbox: http://www.listbox.com

stuart at bmsi

Apr 18, 2010, 7:44 PM

Post #4 of 5 (2451 views)
Permalink

Re: Grammar Requires Backtracking [In reply to]

On Sat, 17 Apr 2010, William Ahern wrote:

> Is anyone else bothered by the fact that the grammar requires backtracking?
>
> Perhaps it would have been wise to have included a %-encoded forward-slash,
> as was done for spaces.
>
> Anybody open to such an amendment?

The immediate need is to incorporate all errata into a non test track
RFC that is as compatible as possible with the existing installed base.

When that is done, there is SPF3, which is just a collection of ideas
at the moment.

--
Stuart D. Gathman <stuart [at] bmsi>
Business Management Systems Inc. Phone: 703 591-0911 Fax: 703 591-6154
"Confutatis maledictis, flammis acribus addictis" - background song for
a Microsoft sponsored "Where do you want to go from here?" commercial.

-------------------------------------------
Sender Policy Framework: http://www.openspf.org [http://www.openspf.org]
Modify Your Subscription: http://www.listbox.com/member/ [http://www.listbox.com/member/]

Archives: https://www.listbox.com/member/archive/1007/=now
RSS Feed: https://www.listbox.com/member/archive/rss/1007/
Powered by Listbox: http://www.listbox.com

julian at mehnle

Apr 27, 2010, 3:11 AM

Post #5 of 5 (2434 views)
Permalink

Re: Grammar Requires Backtracking [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

William Ahern wrote:

> Is anyone else bothered by the fact that the grammar requires
> backtracking? Specifically, because a domain-spec can include forward
> slashes, and because some of the terms allow cidr masks after a
> domain-spec, you have to support backtracking.
>
> Frankly I'm not sure I want to bother supporting this. I use Ragel to
> parse the policies, which is a pure regular langage parser generator. I
> could use Ragel's scanner feature, or just hack the support, but as a
> general rule I don't like backtracking grammars for untrusted input.
>
> Perhaps it would have been wise to have included a %-encoded
> forward-slash, as was done for spaces.
>
> Anybody open to such an amendment?

For "v=spf1" it's never going to happen because it would invalidate a
portion of the existing records.

For another revision of SPF the sky is the limit.

FWIW, I don't understand why you insist on using a 3rd party library for
parsing the SPF grammar. The grammar is rather trivial, really, despite
the need for backtracking.

Or perhaps I'm talking out of my ass because I mostly use languages with
built-in regular expression engines (with backtracking support). Then
again, there's pcre. :-)

> My asynchronous spf.c library passes 90% of the 2009.10 OpenSPF test
> suite (I can't yet simulate timeouts to pass the TempError tests).
> Many, many thanks to those who put in the time and effort to write
> those test specifications.

You're welcome.

- -Julian

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iEYEARECAAYFAkvWuGAACgkQwL7PKlBZWjsW4gCdEz2N+vL4LjEuZWZcepgAtgmw
pb8AnjCjSVuLkxqhxTAgyoIXnWje4j71
=A5D/
-----END PGP SIGNATURE-----

-------------------------------------------
Sender Policy Framework: http://www.openspf.org [http://www.openspf.org]
Modify Your Subscription: http://www.listbox.com/member/ [http://www.listbox.com/member/]

Archives: https://www.listbox.com/member/archive/1007/=now
RSS Feed: https://www.listbox.com/member/archive/rss/1007/
Powered by Listbox: http://www.listbox.com

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads