Introduction
When you start in research you see all these successful people. On Twitter, it seems there is one new game changing paper published every week or so. Here, I want to show the other side, how it is actually a long and painful process to produce good quality research. I believe it is a common story, but not many are talking about it.
“If you want to increase your success rate, double your failure rate.”
Thomas J. Watson, IBM CEO.
It is not said enough. Before succeeding, you fail. It is normal. You should make it your expectation. It is part of the process. Of course, it is painful, especially when seeing the seemingly overwhelming success of everyone around you. Personally, I had to stop going on Twitter because it was too painful to see everyone going forward while I was stuck in the same place for so long. So I feel like it is important to talk about this part of this story so that others do not get disheartened.
We should prepare ourselves for failure, and this is done in large part by surrounding yourself with great, supportive people. I did not aim for it, but looking back, I can see it was crucial to have a great team working with me in CSRC, and a incredible mentor like Professor Cha to help me pivot at the important moment.
Wandering
At the end of the summer of 2017, I had just submitted my first paper. I had this feeling after doing this big thing you have been preparing for a while: “So now what?”.
I knew I did not want to continue on my previous research topic, Linux Kernel security. I did not feel excited about it anymore. So mostly, I was just helping other people in my lab for about six months.
Some people in my lab, CSRC, were working on fuzzing. I did not know anything beyond its basic principles at the time, but it seemed like a very stimulating field. So, I started reading papers in this area. The main point of research that was coming, again and again, was about scheduling fuzzer, so I started considering different options and let my mind wander on this topic.
Then, at the end of year gathering of CSRC, the then chief of center, Sue Moon, asked “How could Machine Learning (ML) help here?”. At first, I kind of dismissed this remark. I thought, ML is just this fancy new topic that everyone is talking about, but does not actually solve anything. Kind of a “higher up do not know what they are talking about” feeling. However, AlphaGo zero got released around the same time. I read the paper, and it got me hooked almost instantly! Reinforcement Learning setup seemed to be matching perfectly the fuzzing situation: There is an agent, in our case the fuzzer, and an environment, in our case the program under test. And the agent is learning about the program by trying different inputs.
The possibilities seemed endless. There are many different techniques, different parts of the fuzzer where it can be applied. How great! So I decided that I will dedicate a few months to explore ideas on how to combine fuzzing and machine learning. As often, this time estimation was way off the mark. In the end, it took two years…
The Fun of Experimentation
Starting a new project in a new area is the best feeling!
“A little magic dwells in each beginning.”
Hermann Hesse
I was fully passionate about the project. I was creating something new from scratch. At each step, I could see my fuzzer improve! The first stage of any fuzzer is just a basic black box fuzzer. Then, you start adding some scheduling deciding which seed the input generation is based on, and you see performance make a huge jump! And then, you add the fitness function, which adds seeds to the pool when they are “interesting“. Again, performance jump! Every time it felt like a shot of excitement.
Of course at the beginning, I was getting to par with the baseline, AFL. Basically, just by rewriting it. But then, once I started improving on it, my brain could not stop thinking. Somehow every day, waking up with a new idea I could not wait to try out. I was learning so much. First about fuzzing: At this point, although I had read a lot of papers, this was my first chance to actually experiment by myself. About machine learning and the libraries used for it.
And one of the first question to answer when applying Reinforcement Learning (RL) anywhere is: what is the reward? This is the goal the agent is aiming for. An RL system is all about maximizing the reward. Based on the reward, the agent decides which action to take and then, how it learns from past actions. It defines the goal of our system. It may look like it should be obvious and already very well defined, but actually it is not. How to benchmark and evaluate fuzzers is a subject of research in itself. So, in my situation, I got to chose, try different reward signals, and see how they perform. I found one on which the RL approach seem to work quite well.
Once the fuzzer was ready, all the elements of the RL framework integrated, I could perform the first meaningful experiments which could validate or disprove the project. It was already a couple of months Ankou was in development. With these first results in hand, it was time to do the first main report. And that is where reality kicked back in. Although I did not want to admit at the beginning, Professor Cha showed me how my project performances were not as good as I thought. It appeared that putting RL in fuzzing was performing very well on the metric I had chosen, but not on all other conventional metrics, like numbers of bugs found or coverage. It was all good to have fun by myself, but at the end of the day, as a researcher, you need to argue you are improving things. And it got clear that Ankou was actually severely underperforming the baseline on the usual metrics.
I was biased because I was too emotionally invested in the project. That’s where I understood the importance of having a guide, or an advisor. Without someone else bringing you back to the “real world”, as a researcher it is far too easy to lose ourself in our ideas. Our mind distort reality to think the project is going well when it really is not. We need an external point of view that is able to understand what we do, but also far enough from it to be able to have an objective opinion on our chance of success.
Painful Persistence
“What’s going wrong? It should work.” That’s the trap I got in. When you have an idea that you think is good, you don’t want to let it go as soon as you see it does not work. Maybe you are “that close” to making it perform as you would like.
At first, I thought Ankou was just too slow because it was just a prototype after all. If I could just make it as fast as AFL, it could work. So I run benchmarks to identify bottlenecks and optimized them. Still, the same bad results.
Then after some more time, I understood the technique was the problem. So I tried all kinds of different Reinforcement Learning algorithms, Neural Network architecture. Maybe neural networks were costing too much in time performance? So I switch to a simplified version of the RL setup, the Multi-Armed Bandit (MAB). And actually, it improved performance. But still not that good, and there was already a paper on improving fuzzing using MAB [1].
At some point, when all the evidence is against you, you should cut your loss short and go on to the next project. But I kept working on this idea for six more months when it was clear after two months that it could not be successful. This period lasted from July to November 2018, and it was quite stressful for me. I had already invested all the time and mental energy. I felt personally invested in it. Until you definitely give up, there is always the chance that it has not all been for nothing.
Eventually, I made a compromise with myself. I decided to take a break on this project. Some kind of personal holiday; To get space in my mind. I had gotten too obsessed with this idea. I was so much into it that I could not think clearly anymore. I was getting too emotional to be able to solve it. I hoped that once I got disengaged, I would be able to see from further away. Maybe a solution that I had not thought about so far would come to mind. Take a step back and let emotions cool down.
The Pivot
Once the pressure to succeed came down, I felt freer to try random things without expecting much from them. In particular, I was thinking about potential visualization for fuzzing, which apriori was not related at all to the RL project. The idea was: There are too many branches to be able to display how many executions there were for a given program run on a usual 2D graph.
While studying statistic, I often came across dimensionality reduction techniques which selects the “best” dimensions to display. If you chose the first two best dimensions, you get yourself a 2D graph! In the RL project, it was usual to consider each branch as an independent dimension. But still, I never thought it would work in fuzzing because there are far too many branches/dimensions to be reduced. But still, for visualizations purpose, it did not cost much to give a try. We could restrain ourselves to the seeds, and there was no time constraint.
One or two days to get the setup right. And bam! The results were amazing! With as little as five dimensions, we could usually get beyond 60% of the space explained! And we could even see some patterns emerge in some dimensions! Below are the firsts results I found back.
Then I was like a kid who got a new toy to play with. This was a new way to understand what was going on inside the program. From the year of working on the RL project, I felt like there was more potential in applying this technique to the fitness function of fuzzers. There might not be so much margin of improvement in fuzzers’ scheduling after it was researched so much.
But then, dimensionality reduction was a nice shiny new toy, but it had a drawback: it is so expensive to compute! So I needed to optimize the PCA (Principal Component Analysis), the way dimensionality reduction is usually implemented. Otherwise, it would not work for fuzzers. I was back in the exciting phase of the project beginning. Trying to come up with a new algorithm.
I got a little lost in the linear algebra. I studied it a little in my first years at university, but now I needed to really get into it if I wanted to make changes to the PCA algorithm. That’s where Soomin came to my rescue! With his help we could eventually succeed in optimizing the algorithm ended up in the “Dynamic PCA” (I let you read the paper learn more about this 😉) [2].
From there, we had to scale the experiment and had some other experiments problem. The results were good, so we kept feeling positive. The last line towards submission is always a lot of work. We had to make sure all experiments were statistically significant. Many re-written drafts of the paper so that it is as easily understandable as possible. Nevertheless, although somewhat stressful, this last line made me less anxious because there was less uncertainty on whether or not we could make it. You just got to put up the work. A couple of short nights at the end; Submitting successive updates five minutes before the deadline. And finally we reached the end!
The time after submission is always a little weird. Suddenly, the tension relaxes, but you are still thinking of this work which is currently being judged. We were luckly enough to have great reviewers with good comments on how to improve the paper. So the paper got accepted at its first submission 🎉.
Conclusion
I learned many lessons in this journey. Do not get too stuck on your idea. Perseverance is important, but you need to know when to cut your losses short on move on. Turn the page and pivot. The best way to prepare yourself for this challenge is to chose the good people to surround yourself with.
[1] Scheduling Black-box Mutational Fuzzing, CCS 2013
[2] Ankou: Guiding Grey-box Fuzzing towards Combinatorial Difference, ICSE 2020
* There is a translated version of this article for Korean.
3 명이 이 글에 공감합니다.