Bug 1159 - poly1305 unit tests
Summary: poly1305 unit tests
Status: RESOLVED FIXED
Alias: None
Product: Libre-SOC's first SoC
Classification: Unclassified
Component: Milestones (show other bugs)
Version: unspecified
Hardware: PC Linux
: --- enhancement
Assignee: Sadoon Albader
URL:
Depends on: 1157
Blocks:
  Show dependency treegraph
 
Reported: 2023-09-10 17:27 BST by Sadoon Albader
Modified: 2024-05-27 13:52 BST (History)
4 users (show)

See Also:
NLnet milestone: NLnet.2021.02A.052.CryptoRouter
total budget (EUR) for completion of task and all subtasks: 0
budget (EUR) for this task, excluding subtasks' budget: 0
parent task for budget allocation: 840
child tasks for budget allocation:
The table of payments (in EUR) for this task; TOML format:
#sadoon=0 #lkcl=0


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Sadoon Albader 2023-09-10 17:27:24 BST
a test matrix is needed which copes with poly1305 having some
rare-occurrences of "carry-roll-over" internally.  a strategy is
needed which detects some of these occurrences, then puts some
test vectors together to ensure that the assembler (which is much
slower to run) also passes.

the one that will have confidence that such errors will not occur is
the pure-python Poly1305 class which performs full python "Long"
integer arithmetic. this can be used to help track down
potential/actual 64-bit carry arithmetic errors.

for this strategy to work it is important that the assembler
(and poly1305-donna.py) faithfully implement the poly1305-donna-64bit.h
algorithm exactly.

---

* TODO strategy to deliberately introduce carry-rollover errors
  (to create test vectors to run against the assembler)
* TODO miniature unit tests of fragments of poly1305-donna.py
  (to be used also against test_caller_svp64_poly1305.py)
* TODO comparison matrix against:

1. python Poly1305 class instance
2. python Poly1305Donna class instance
3. c-based wrapper module around poly1305-donna.h
4. SVP64 assembler (in test_caller_xxxyyy.py)
5. pypowersim running svp64.
Comment 1 Sadoon Albader 2023-09-20 17:54:57 BST
Rough brainstorming:

To implement comprehensive unit tests we need to understand what we're testing, figure out the normal cases, edge cases, and additional behavior that is specifically related to SVP64.

I'll organize this list in order of complexity.

numbers are in bytes,
m = message, k = key, h' = received MAC, h = generated MAC 


Message size:

-m[0] is received, nothing to authenticate, exit

- m[16] is received, algorithm needs to process exactly one block and is done.

- m[16*n] is received, algorithm needs to process exactly n blocks using the same function and is done.

-m[1<n<16] is received, algorithm needs to process leftover data as opposed to full data (I have to study this a bit more)

-m[17<n] where n%16=/=0 received, algorithm processes n/16 blocks normally and the last block is processed as leftover.
Comment 2 Luke Kenneth Casson Leighton 2023-09-20 18:59:34 BST
(In reply to Sadoon Albader from comment #1)
> Rough brainstorming:
> 
> To implement comprehensive unit tests we need to understand what we're
> testing, figure out the normal cases, edge cases, and additional behavior
> that is specifically related to SVP64.

so just like in the Test API, there are actually *three* things
to test (all with the same data). actually 4 when it comes to it.
no, 5! no 6!

1. python Poly1305 class instance
2. python Poly1305Donna class instance
3. SVP64 assembler (in test_caller_xxxyyy.py)
4. HDL (when it is able to run REMAP and elwidth overrides)
5. pypowersim (this is "optional" for you as it is extra work)
   running the poly1305-donna.h program compiled to *SFFS* which
   you would be converting slowly using (3) to...
6. pypowersim running svp64.

but i would suggest stopping at (3), i will happily sign-off the entire
RFP up to there :)

nice thing is, you can actually write the unit tests *right now* for 1 and 2
but please do also write some "mini" intermediary unit tests for each
group of 3-6 lines (a group doing h0+= h1 += h2 +=) so that you are
*truly* confident that each group does the job; then when you come to
plug all those "bits" together you will go "pffh, i *know* this should
work"
Comment 3 Sadoon Albader 2023-09-22 20:01:40 BST
(In reply to Luke Kenneth Casson Leighton from comment #2)
> (In reply to Sadoon Albader from comment #1)
> 1. python Poly1305 class instance
> 2. python Poly1305Donna class instance
> 3. SVP64 assembler (in test_caller_xxxyyy.py)

1. and 2. are simple enough, I've already added some known-working values from the original poly1305-donna project and they do work fine. Importantly, they are *not* multiples of 16-bytes and not less than 16-bytes which should put any implementation through its paces.

But for a proper unit test I think at least 10 vectors with different sizes and different keys should be added, which I will do before attempting anything else.

I've been reading https://libre-soc.org/docs/firststeps/ to better understand how test_caller_* works, is there any other relevant documentation to help steer me in a good direction? Not necessary as I feel I already understand 80% of how it works, but nice to have if available.

EDIT: forgot one more thing: in addition to the 10 vectors, I'd also add a function that generates random data of random sizes and random keys and tests using all 3 implementations.
Comment 4 Luke Kenneth Casson Leighton 2023-09-22 21:43:39 BST
(In reply to Sadoon Albader from comment #3)
> (In reply to Luke Kenneth Casson Leighton from comment #2)
> > (In reply to Sadoon Albader from comment #1)
> > 1. python Poly1305 class instance
> > 2. python Poly1305Donna class instance
> > 3. SVP64 assembler (in test_caller_xxxyyy.py)
> 
> 1. and 2. are simple enough, I've already added some known-working values
> from the original poly1305-donna project and they do work fine.

git push! always always always push immediately. this is a key project
workflow procedure.

> Importantly,
> they are *not* multiples of 16-bytes and not less than 16-bytes which should
> put any implementation through its paces.
> 
> But for a proper unit test I think at least 10 vectors with different sizes
> and different keys should be added, which I will do before attempting
> anything else.

push the existing ones first. you'll see in HDL_workflow the
rule is 5-15 lines of code per commit (with exceptions of course)

> I've been reading https://libre-soc.org/docs/firststeps/ to better
> understand how test_caller_* works, is there any other relevant
> documentation to help steer me in a good direction? Not necessary as I feel
> I already understand 80% of how it works, but nice to have if available.

not really... there are however hundreds of unit tests, they are all the
same. i just cut/paste an existing one, test_caller_svp64_chacha20.py
is your best bet.

> EDIT: forgot one more thing: in addition to the 10 vectors, I'd also add a
> function that generates random data of random sizes and random keys and
> tests using all 3 implementations.

awesome.

and that puts the work you're about to commit right now at way above the
limit for commits? :) that's 3 separate commits you should have made,
just in the past hour alone!

this is how we can do review.

nobody else can see your screen nor what is on your local hard drive.
Comment 5 Sadoon Albader 2023-09-23 09:57:08 BST
(In reply to Luke Kenneth Casson Leighton from comment #4)
> (In reply to Sadoon Albader from comment #3)

> git push! always always always push immediately. this is a key project
> workflow procedure.

When I said "added" what I really meant was I was messing around with the code and *replaced* the original values :P
I'll push it once it's actually added as opposed to replaced of course.


> not really... there are however hundreds of unit tests, they are all the
> same. i just cut/paste an existing one, test_caller_svp64_chacha20.py
> is your best bet.

Yes I noticed after sending, the tests are quite simple to write so I should have 80-90% of what we need done by next weekend.

> this is how we can do review.
> 
> nobody else can see your screen nor what is on your local hard drive.

Most of what I sent was more of a brainstorming than actual code being written. So far the only change I made was the message and key to test against poly1305-donna, the rest is what I plan to write and then push, and of course, gradually. Not one huge commit-git-push :)
Comment 6 Luke Kenneth Casson Leighton 2023-09-23 11:21:51 BST
(In reply to Sadoon Albader from comment #5)

> When I said "added" what I really meant was I was messing around with the
> code and *replaced* the original values :P

yyeah i did that too :)

ah this is a... it just occurred to me, of course the tests will be
very specific to the algorithm internals, it will be quite fragile.
as in: if you don't *exactly* faithfully replicate the poly1305-donna
algorithm (even from the original c) then you could end up missing
something important, as it is so rare an occurrence.

hm i tell you what, i will create a python wrapper around poly1305-donna.h
so that *that* can also be added to the test matrix. i won't do the
unit tests themselves (other than a real basic one), just to get it
not to segfault ok?

then you can run huge numbers of tests very quickly, on the c-based
module *and* the poly1305-donna.py conversion, and at least have a
degree of confidence that i did the conversion correctly!

we *must* make sure that there is a "chain of confidence", absolutely
no more than one "unknown" at any one time, no matter how small and
"seemingly ridiculous" ok?  just like in that word game.
Comment 7 Sadoon Albader 2023-09-23 11:37:11 BST
(In reply to Luke Kenneth Casson Leighton from comment #6)
> (In reply to Sadoon Albader from comment #5)
> 
> we *must* make sure that there is a "chain of confidence", absolutely
> no more than one "unknown" at any one time, no matter how small and
> "seemingly ridiculous" ok?  just like in that word game.

Sure :)
Comment 8 Luke Kenneth Casson Leighton 2023-09-23 11:53:45 BST
siiiigh i don't know if you worked it out already sadoon, we need to
*actually find* places where carry-roll-over errors might occur,
and put specific values in that ensure they get tested.

argh :)

ok so some random tests are needed with an "accumulator list" when
there are non-zero carrys... eurgh :)
Comment 9 Sadoon Albader 2023-09-23 11:56:26 BST
(In reply to Luke Kenneth Casson Leighton from comment #8)
> siiiigh i don't know if you worked it out already sadoon, we need to
> *actually find* places where carry-roll-over errors might occur,
> and put specific values in that ensure they get tested.
> 
> argh :)
> 
> ok so some random tests are needed with an "accumulator list" when
> there are non-zero carrys... eurgh :)

Not quite yet, will do this week though.
Comment 10 Luke Kenneth Casson Leighton 2023-09-23 14:44:52 BST
(In reply to Sadoon Albader from comment #9)

> Not quite yet, will do this week though.

am bored am on the case, am going to do some "decorators" to trap
the ADD MUL ADDLO and SHF functions, trying hard to make the code
"look like it's still the c code"

i'll get it to print out a list of what it finds, just realised
that when c=0b000 this is still a legitimate test-case not just
c=0b001 to 0b100

first step: convert all use of "+" to call ADD(a,b)
https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=539eda3c
Comment 11 Luke Kenneth Casson Leighton 2023-09-23 16:03:56 BST
next step in the (word-game-like) chain: rename the 64/128-bit math
primitives, provide intercepts in the class, but provide *function-local*
renames so that the code remains true to poly1305-donna-64bit.h
https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=8cd4e8272a

btw i'm not going to do all of this! i'm providing _you_ with the pieces ok? :)
Comment 12 Luke Kenneth Casson Leighton 2023-09-25 14:37:14 BST
carrying on from https://bugs.libre-soc.org/show_bug.cgi?id=1157#c26
the strategy needed is quite involved but straightforward: anything
looking like it is carry-roll-over has to be reproduceable / replayable
against *other implementations* of the algorithm.  that in turn implies
capturing *all* state information at the time of the math-operation.

therefore what i am going to do is do a... what is it called...
Context Manager that allows full input/output capture, in a clean
and clear way.
Comment 13 Luke Kenneth Casson Leighton 2023-09-25 19:12:22 BST
(In reply to Luke Kenneth Casson Leighton from comment #12)

> therefore what i am going to do is do a... what is it called...
> Context Manager that allows full input/output capture, in a clean
> and clear way.

https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=6479aa6ed404829f6a1eab296b42be772b532e39

done partly, i am working out how to make it clean. i also realised
that this technique potentially could be used to *auto-generate*
the required unit test values but it may be better explicitly spelled
out?
Comment 14 Sadoon Albader 2023-10-03 16:23:49 BST
(In reply to Luke Kenneth Casson Leighton from comment #13)
> (In reply to Luke Kenneth Casson Leighton from comment #12)
> 
> > therefore what i am going to do is do a... what is it called...
> > Context Manager that allows full input/output capture, in a clean
> > and clear way.
> 
> https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;
> h=6479aa6ed404829f6a1eab296b42be772b532e39
> 
> done partly, i am working out how to make it clean. i also realised
> that this technique potentially could be used to *auto-generate*
> the required unit test values but it may be better explicitly spelled
> out?

Just had the chance to look at this, brilliant.

I'll try to start and finish the test suite that generates random messages and keys and tests against the poly1305-donna C implementation tonight. Speedrun time to catch up :)
I'll push whatever is ready.
Comment 15 Luke Kenneth Casson Leighton 2023-10-03 16:40:09 BST
(In reply to Sadoon Albader from comment #14)

> Just had the chance to look at this, brilliant.

bit of a hack but the context manager helps a lot

also perhaps useful (at some point) is to capture the *instance*
arguments so that those link back to the input that *caused*
whatever intermediary variables to have their values, such that
you can create a *top level* unit test that happens to reproduce
those exact intermediaries.

> I'll try to start and finish the test suite that generates random messages
> and keys and tests against the poly1305-donna C implementation tonight.

ah it is much simpler (like... 2 minutes vs 1 hour simpler) to test
against the *python* poly1305.py

the advantage is that the python poly1305.py uses arbitrary-length
precision math and is therefore bloody obvious not to have any carry
rollover errors.
Comment 16 Sadoon Albader 2023-10-03 16:42:15 BST
(In reply to Luke Kenneth Casson Leighton from comment #15)
> ah it is much simpler (like... 2 minutes vs 1 hour simpler) to test
> against the *python* poly1305.py
> 
> the advantage is that the python poly1305.py uses arbitrary-length
> precision math and is therefore bloody obvious not to have any carry
> rollover errors.

I seem to have misunderstood then, aren't we supposed to test against both the python and C implementations, since the C one is being used as the source that we ported to python and then porting to SVP64?
Comment 17 Sadoon Albader 2023-10-03 17:25:47 BST
At any rate the C unit test is done, output is conveniently in CSV format (lol)

This means we can use pure python to convert the 3 arrays, now figuring out the correct output formatting needed before pushing.

EDIT: I don't have permissions to push to openpower-isa, could someone please add me?
Comment 18 Luke Kenneth Casson Leighton 2023-10-03 17:51:24 BST
(In reply to Sadoon Albader from comment #16)

> I seem to have misunderstood then, aren't we supposed to test against both
> the python and C implementations, since the C one is being used as the
> source that we ported to python and then porting to SVP64?

yes? :) i tend to think in terms of "shortest path"...

(In reply to Sadoon Albader from comment #17)
> At any rate the C unit test is done, output is conveniently in CSV format
> (lol)

niiice. see csvreader although
 with open(fname) as f:
   map(lambda x : x.split(","), f.readlines())
does the same job in 2 lines...
 
> This means we can use pure python to convert the 3 arrays, now figuring out
> the correct output formatting needed before pushing.
> 
> EDIT: I don't have permissions to push to openpower-isa, could someone
> please add me?

eep 1 sec.. done
Comment 19 Sadoon Albader 2023-10-03 18:45:39 BST
Confirmed working but the python edits are dirty, cleaning up and pushing in a bit.
Comment 20 Sadoon Albader 2023-10-03 19:27:08 BST
Pushed to master, only added new files so no point in creating new branch this time around.

https://git.libre-soc.org/?p=openpower-isa.git;a=commit;h=200ebca86abc2f5535cf02fc64f1b379a9fede5f

It's 5 commits but this is the last one as of today.

Woohoo!
Comment 22 Luke Kenneth Casson Leighton 2023-11-30 09:43:31 GMT
sadoon shriya this is worth studying what jacob has done here.
https://bugs.libre-soc.org/show_bug.cgi?id=1044#c72
it is also how i recommended to tackle this one, through an
incremental extremely patient "ONLY a few assembler lines at a time"
approach.