Hello, I am Marianne, I work in Cust, and today I will present my work done in GCC, which
is already merged into upstream, its CRC detection and optimization.
CRC, or cyclic redundus, is used to detect errors in digital digital data transmission,
and CRC generated checks based on the input data.
There are many CRC implementations in software, for example, Bitwise method, which is very
slow, careless multiplication based method, and table based method.
And there are many projects that use Bitwise CRC implementation, which I already taught
with work slowly, and here are some examples from real-world projects.
And so, as I already told with Bitwise is slow, we want to detect Bitwise implementations
in projects, and when replaced with faster ones, for example, if the hardware already has
CRC instruction, we will use it, or not if it has careless multiplication instruction,
use careless multiplication instruction, if neither of those instructions are supported.
We generate table based CRC, and how we detect CRC's Bitwise CRC's.
It consists of two main stages, first is initial checks, and the second is verification.
So, firstly, we do some simple checks to filter out known CRC's, and afterwards, we
verify those by using symbolic execution.
Now, what we do in initial checks, here I will slightly say what we do, but actually we do more deep
and complex analysis.
We detect the loop, which iteration is 8, 16, 42, or 64, in this case it's 16, and it must be the
innermost loop.
Also, contain if condition and under it, accelerate operation.
Also, there must be a shift operation, in this case shift left we have.
So, we do some kind of checks, after what if two criteria are okay, we verify those.
All these things are done on-game representation, for what I have added separate paths.
So, here is broke the green presentation of this loop, what we have here, and afterwards comes verification.
So, to verify what this is really CRC, we create a LFSR for the polynomial, symbolically execute the loop,
and when check what LFSR and the output of the execution match.
So, what is polynomial, XCRC has its polynomial.
So, CRC is the remainder of a modular to polynomial division of the data.
In this case, we have this polynomial, and polynomials are represented by binary numbers.
Here we have the coefficients, where we have one, here we have one, and our values are zeros,
and in the example above, leading one is omitted.
So, there is use this value, but it is the polynomial.
And what is LFSR? LFSR stands full in your feedback sheet register.
LFSR is a register, where the input depends on the linear function of its previous text,
and with LFSR we can calculate CRC.
Here, this LFSR calculates CRC with the following polynomials.
In the places where coefficients is one, we have XOR operation.
Here, just this one is used only for first one, and the second.
And how we create LFSR structure for us, we execute the loop, firstly we have some specific values,
to extract the polynomial, because in CRC it is not always obvious,
which is the polynomial, and when create LFSR, using that extracted information.
Also, during initial checks, we extract some more information about CRC, its size,
shift direction, and so on, and here is created LFSR structure for the above example.
Here is used the following polynomial, it is in binary representation.
And here we have shift left, because of that we got this LFSR, here we gave symbolic values,
and in square braces, we have the fit position.
So here we have CRC 15, if it shifts left, it will come to a front, and CRC 0 is moved one bit left.
So, after doing all these things, we execute the loop, fifth symbolic values.
For example, here CRC doesn't have any concrete value, because of that, we gave it some symbolic value,
and execute the loop on a bit level, because of it, I gave a number of positions.
And after that, we track each variable on each part.
So, after this CRC got its symbolic values, after what we calculate CRC 9 variables value,
which is shifted back one bit, so we got 0, and after what CRC 14, 0, and so on.
When we calculate the value of variable 7, and here comes the conditional, if so, after what we have two branches,
as we don't know the value of 7, we will execute both branches.
So, we duplicate the state, create a new state for the false branch, and first we can go by true branch,
and afterwards continue from the false branch.
So, for the true branch, we keep the condition.
So, if 7 is less when 0, it means that the last bit is 1, and in case it's positive, it will be 0.
Because of it, we hear it, but last bit equals to 1, and for the false branch, last bit equals to 0.
After what, for true branch, we will calculate CRC 10th value, and continue.
And here, this CRC is for us interesting. We get its value, and we also have what CRC 15 equals to 1.
Also, this is our final state for true branch, and we also continue for false branch.
For the false branch, we will have that CRC 1, so while you is the following, and the condition is what CRC 15 equals to 0.
After the execution, after one iteration, we have two states and variable values.
After what, we check what those conditions will be with God, much the LFS are what we created.
Above is the LFS are what we have created, and these two are those what we got.
So, for true branch, we had what CRC 15 equals to 1, so if we put it in there, we will have here 1, CRC 0, etc.
After what CRC 4X or 1, and so on, and as you can see, it marks. For the false branch, it marks 2, because if we put 0, instead of CRC 15, we will have 0, CRC 0, and so on.
So, we got what the CRC what we found is real CRC.
And, after what, we replace what we found, we foster CRC versions.
For what, we instead of for loop, put internal function, it may be table based implementation, cell move based or direct CRC based on the hardware.
Here is how we generate cell move based. It's in assembly, but here I show in some kind of our way, so it is more understandable.
Here is how we generate table based, and about the result.
We have verified free Bitcoin CRC implementation in Linux kernel. Here is one example, but also we verified 19 Bitwise implementations in Fedora packages.
Here are also some examples.
Also, we checked edit 24 CRC cases, and 12 not CRC cases, to check how good our detection works.
So, the true positive rate is 21, false negative is free, but false positive is 0.
So, we implemented our algorithm in such way that we don't get any false positives, because if we change wrong CRC, so if it's not CRC and we change it, the code will work not correctly.
Because of what we have false negative, so we don't find all cases, but what we find is real CRC.
Also, we have tested how fast works, those optimized versions. Here is test on x8664.
We ran CRC FFF times to check how fast it works. So, we here gave out many different CRC with different sizes and different data sizes. Here is not all the cases, but in average it gave 54% improvement for the table based generation, and 43% for sale based generation.
So, here is the time for bitwise how long it works, how long works table based, how long worked sale move based. For example, in this case we got 91% improvement.
Also, we checked on risk 5. Here we got 66% improvement on table based generation on ARxistic for we got 50% improvement.
And here are examples for CRC 42 instruction. In this example, we didn't have CRC 42 instruction how was working. Here are some other tests, but use CRC 42 instructions polynomial.
And here are table based CRC 42 instructions. If you can see CRC 42 works the fast test. And here are results for ARxistic for, and here we got 93% improvement. But for table based it's slow down.
And here is average improvement for free ARxitectures and the promise for free cases.
Also, we have published an article. There is written more deeply how everything works.
Thank you.
Did you work on detecting other types of CRC algorithms such as the table based and?
No, we worked only bitwise CRC. If there is a CRC instruction, the 9 bitwise implementation ends up being the best, which is the same.
It's hardware instruction and it's implemented in better way. So if you replace whole for loop with one instruction, it works better. But for table based and CRC 2, more operations. So it takes more time.
So hardware CRC instruction works faster and to swear software implementation, what I show you.
So how is this enabled? This element would be just special. And the second is this on the jibble.
Okay, first question. How it's enabled? There is minus f CRC flag, but enables. And also it's enabled by default.
Starting from all two optimizations. And here are two parts, first part for the detection part. I added a pass, separate pass.
It works on gimpon. And after the replacement part is vacant. So we put internal function and for x808664 and ARx64 and bit risk 5. I added expender. So with expender, I generate either table based, either cell-mull based or direct.
CRC instruction. But CRC is only for 32 bit. Now hardware has support. So CRC 42 instruction, not always we can use, because it's polynomial is also specific. So we check if it is what CRC we use CRC in other ways, we use a mobile based or table based.
Okay. So you show statistics by the IRC RL for this process. But the whole population is only 23 things. And just certainly not enough to have a pass like this. We need to act for proof that it will not do the whole thing.
The proof is that the algorithm is written in such a way that there can be false positive, because it comes from the algorithm.
So my question is, what are the invitations on the debug view for here?
The debug information is lost.
No.
I'm curious why the detection not work for those three cases that we show. The false negatives.
Yes, there are some cases where we don't find there is limitations. For example, if the implementation used the polynomial, where leading one is not emitted, we can detect, because for example, if you use CRC 8 to keep the polynomial with one.
We didn't beat, you will use 9 bit. Yes, because what you will go into for example, 16 bit memory.
And for what we can't know exactly, you wanted to calculate 16 bit CRC or 8 bit CRC with leading one polynomial, for example.
And there are some other cases where we don't detect. Now that was one example.
You want to live home for future invitations.
In some cases, table based work slower when they are moved based. It comes from the implementation. Here we have good persons, but for example, in these cases we got better results.
It comes because here CRC 42 is a bit backwards CRC. So in that case, we have to reflect input value and reflect output value and more times goes to reflect those values.
Because of that, it worked slower. But if you use some, for example, instructions where we will reflect very fastly, better algorithm to reflect the value, it will work faster.
Just now the implementation's use not what fast method.
Thank you.