Bouwers > Eric > Blog

A last post?

2011-08-28T16:49:00.002+02:00

It took some time to actually post it here, but I am very pleased to say that the paper "Dependency Proﬁles for Software Architecture Evaluations" by Bouwers, van Deursen and Visser has been accepted at the Early Research Achievements-track of the 27th IEEE International Conference on Software Maintenance.

Before dumping the abstract I want to confess that I have given in and created a twitter-account. As you might have noticed, my updates have been infrequently at best. This is mainly because it takes me a long time before I start writing. Let's see whether this twitter-thing makes this easier!

Abstract:
In this paper we introduce the concept of a “dependency profile”, a system level metric aimed at quantifying the level of encapsulation and independence within a system. We verify that these profiles are suitable to be used in an evaluation context by inspecting the dependency profiles for a repository of almost 100 systems. Furthermore we outline the steps we are taking to validate the usefulness and applicability of the proposed profiles.

WICSA 2011

2011-04-04T15:00:00.002+02:00

And yet another publication to announce! I am very happy to tell you all that the paper "Quantifying the Analyzability of Software Architectures" by Bouwers, Correia, van Deursen and Visser has been accepted at the 9th Working IEEE/IFIP Conference on Software Architecture!

Abstract:
The decomposition of a software system into components is a major decision in any software architecture, having a strong influence on many of its quality aspects. A system’s analyzability, in particular, is influenced by its decomposition into components. But into how many components should a system be decomposed to achieve optimal analyzability? And how should the elements of the system be distributed over those components?
In this paper, we set out to find answers to these questions with the support of a large repository of industrial and opensource software systems. Based on our findings, we designed a metric which we call Component Balance. In a case study we show that the metric provides pertinent results in various evaluation scenarios. In addition, we report on an empirical study that demonstrates that the metric is strongly correlated with ratings for analyzability as given by experts.

(and yes, maybe twitter is not such a bad idea if I keep on writing these short posts :)

SQM 2011

2011-03-02T13:28:00.000+01:00

Yes I know, it is a bit late. However, I am still very pleased that the paper Preparing for a Literature Survey of Software Architecture using Formal Concept Analysis by L. Couto, J.N. Oliveira, M.A. Ferreira and E. Bouwers has been accepted (and presented) at the Fifth International Workshop on Software Quality and Maintainability!

The abstract:

The scientific literature on Software Architecture(SA) is extensive and dense. With no preparation, surveying this literature can be a daunting task for novices in the field. This paper resorts to the technique of Formal Concept Analysis (FCA) in organizing and structuring such a body of knowledge. We start by surveying a set of 38 papers bearing in mind the following questions: “What are the most supported definitions of software architecture?”, “What are the most popular research topics in software architecture?”, “What are the most relevant quality attributes of a software architecture?” and “What are the topics that researchers point out as being more interesting to explore in the future?”. To answer these questions we classify each paper with appropriate keywords and apply FCA to such a classification. FCA allows us to structure our survey in the form of lattices of concepts which give evidence of main relationships involved. We believe our results will help in guiding a more comprehensive, in-depth study of the field, to be carried out in the future.

A new year, a new set of chances

2011-01-02T14:04:00.008+01:00

At the end of the old year (or the start of the new year) there is usually some time to clean up the old stuff and get around to the things you keep postponing.

In my case, I finally got around to put the slides of my Landelijk Architectuur Congres (National Architecture Congress) presentation on-line. Currently the slides are in Dutch, but fortunately I got an invitation to present the work to an English audience. A nice chance (and 'stick-behind-the-door') for me to translate the slides.

And although it might be a bit late (the deadline is just around the corner), the new year still offers you a chance to participate in the Second Workshop on Managing Technical Debt 2011, to be held on the 23th of May.

It might be fun to try to explain what 'Technical Debt' is and why you should care about it, but I believe others already did this better than I could. So let me just point you to this post of Philippe Kruchten, which contains all the information and links you need to get started. Looking forward to your contributions!

Attending LASER 2010

2010-10-03T16:15:00.004+02:00

Today I managed to go through my notes of the 2010 edition of the LASER summerschool series. While doing this I realized that, apart from the fancy hotel, the good food, the nice people and the great weather, the trip also had a high educational value!

Walter Tichy explained several important aspects, which I need to take into account while designing my next empirical study.
In addition, Natalia Juristo pointed out several things I will keep in mind during this design in order to make sure others can repeat it.
Tim Menzies gave a very good introduction into the ins and outs of data-mining (in such a way I actually want to try it out)
Bertrand Meyer (and his students) made me aware of some testing techniques I forgot about.
The presentation of Joshua Bloch was, for me, less relevant from a PhD point-of-view, but his thoughts about good API design are extremely interesting from a developers point of view.
It was really fun (and interesting) to hear Barry Boehm explain his research on estimation models and how empirical SE can be integrated into education.
Last but not least, the presentations of Victor Basili contained a lot of stuff which I believe is relevant for what we are doing at SIG.

Now, all we have to do is to figure out how we can free up some time to apply all that we learned :)

A magazine article

2010-09-18T13:32:00.006+02:00

This week I received some hard-copies of the July/August issue of the IEEE Software magazine. This issue contains an article called
A Lightweight Sanity Check for Implemented Architectures
which is written by Arie van Deursen and yours truly.

The article looks really great, it has multiple colours, pull-quotes, a side-bar and pictures! And although good looks are sometimes deceiving, this article also contains some pretty interesting content (if I do say so myself).

As expected, it describes a check-list which can be used to get a quick overview of the state of the implemented architecture of a system. Such an overview helps in determining which parts of the architecture can be improved, or confirms that everything is in good shape. I believe that both outcomes are interesting, so I recommend everybody to give LiSCIA a try!

A 5 star system!

2009-11-19T20:59:00.005+01:00

My presentation on JFall 2009 went very well, there was a big audience (they barely fit into the room) and there was lot's of interaction going on during the talk. People where asking critical questions and provided good comments.

The topic seemed to make people pretty enthusiastic. Especially the examples of a really complex method, the biggest method and a method with a lot of parameters.

In the presentation I answered the following two questions: 1) what is a 5-star system, and 2) how can I get one? The answer to the first question is: "a system that receives the highest rating in the TUVit Trusted Product Maintainability Certification". I explained what this certificate entails and how the complete procedure works (something which is also summarized over here).

The second question is answered by the following mantra: "make sure that your code is small, simple and specific".

If you cannot make your code small, simple and specific, take a step back and look at the abstract picture (the overall design) of your project. Why does this design disallow you to make your code small, simple and specific?

Can you model stuff differently? Is there a way to abstract over details that clutter your code? How can this type of functionality be grouped in a better way? Try to determine why the design (or your framework) is restricting you and solve that problem. The result will be a more maintainable system.

Naturally, these answers are just the core of the talk, a more complete overview of the presentation is provided by the Atos Application and Development blog (Dutch). For those interested, the slides can be found here.

All and all a nice experience, on to JSpring 2010!?

A 5 star system?

2009-10-11T14:54:00.003+02:00

This week I received notice that my proposal for a presentation at the J-Fall 2009 was accepted. So on the 11th of November I will be discussing what a 5-star system is and how to get it. For those of you who cannot wait to find out what it means to get stars for your system can take a quick look over here.

The full abstract of the presentation can be found here (in Dutch). If you want to attend you should register yourself over here.

Hope to see you in Bussum!

I present, you present ....

2009-09-27T16:28:00.007+02:00

Last week I was in Canada for the ICSM 2009 (combined with a very relaxing vacation btw) where I got to present my first paper of my PhD. The room was a filled with about 50 attendees and, even though I was a bit nervous, the presentation went pretty well. There where some interesting questions and comments, and even a small discussion that had to be taken off-line (which is now again on-line).

During the rest of the ICSM I talked to various people about the presentation and the paper and it seems that the topic certainly appeals to several people. Which is good to know since I think I will be spending some more time in researching it.

For those of you that are interested in the slides, please take a look at the slides page of the ICSM, or just follow the direct link.

To be honest, these slides are not exactly the ones I used during the presentation. I cheated a little bit by splitting a slide 22 in two slides, just so that you can actual see the contents of a table. In the original version there was an animation that removes the numbers before showing the crosses, but this behavior is not transferred to the pdf-version of the slides. I can tell you from personal experience that it will increase your blood pressure if you notice this when you are giving your presentation.

Anyhow, at least I learned now to check the pdf-version of my slides before I give I a presentation, just in case the laptop on which I made the presentation does not play nicely with the available beamer :)

A first chapter

2009-05-31T15:25:00.003+02:00

Yesterday morning at about 5.48 am I received an email with the following message:

We are pleased to inform you that your paper, entitled
Criteria for the Evaluation of Implemented Architectures
has been accepted for publication as a FULL RESEARCH PAPER in the conference proceedings.

The e-mail was send by the ICSM 2009 Research Program Co-Chairs. It also explained that out of the 162 research papers submitted, 35 were accepted as full research papers (21.6% acceptance ratio). A nice beginning of my PhD thesis :)

Abstract:

Software architecture evaluation methods aim at identifying potential
maintainability problems for a given architecture. Several of these
methods exist, which typically prescribe the structure of the
evaluation process. Often left implicit, however, are the concrete
system attributes that need to be studied in order to assess the
maintainability of implemented architectures.

To determine this set of attributes, we have performed an empirical
study on over 40 commercial architectural evaluations conducted during
the past two years as part of a systematic ``Software Risk Assessment''.
We present this study and we explain how the identified attributes can be
projected on various architectural system properties, which provides an
overview of criteria for the evaluation of the maintainability of implemented software architectures.

Solving bad smells

2009-04-14T20:13:00.005+02:00

Last week I took some time to checkout the JDeodorant Eclipse plugin. The plugin was introduced to me at CSMR 2009 by Nikolaos Tsantalis. The demo he gave me already showed some potential, and playing around with the plugin confirmed this first impression.

Installing the plugin was easy, I just followed the installation instructions on the website. At first I used the tool on one of our smaller projects to find refactorings for long methods. After some minutes the results showed a long list of refactor-candidates. Unfortunately, this lists also contained many propositions to move, for example, all statements of a method to a new method. Even though it is a theoretically correct proposition it does not really make sense in general.

Since I did not feel like analyzing the complete list I tried a different approach. I first used checkstyle to find potential candidate methods and let JDeodorant analyze these files one at a time. This does not only speed up the process of finding the candidates, it also provides a list that is way easier to handle. Using this approach I found some new ideas for a several smaller refactorings in just a few minutes.

In the end I think that, even though it still has some rough edges, this plugin can be very useful. Anyway, the plugin is definitely put onto my watch list.

SQM and CSMR 2009

2009-03-29T17:02:00.005+02:00

Last week, I was in Kaiserslautern to attend the 2009 version of SQM and CSMR. Both the workshop and the main conference were hosted at Fraunhofer IESE, which turned out to be an excellent host.

All of the conferences I have attended up until now lasted only for a day, so I did not really know what to expect of four days of presentations. I was a little bit afraid that I would not be able to pick up any new information on the last day, but everything turned out to be fine. Every day brought at least two interesting presentations, and definitely one interesting conversation about the current research somebody is doing. I have met several interesting people (who might be interested in doing some research together), and picked up quite a few new ideas. Unfortunately, it is too much to write down all at once, but I will try to post updates on this on a more regular basis.

What I found particularly interesting was the fact that several people mentioned the same two things on various occasions. The first one is that PhD students should not start from scratch when they are implementing their ideas. Although some students are using more generic development frameworks (like for example Eclipse), there are still people out there that start everything from scratch. This does tend to take up a lot of time and usually results in tools that "should be publicly available before I finished my thesis, I just want to clean it up a bit first". I am not really sure how this problem can be solved (and neither did the people at the Industry Panel Discussion), but I do hope that my future tools will not suffer the same fate.

The second thing that was repeated a few times is the call for more empirical evidence for the usefulness of ideas and tools. However, the lack of publicly available industrial systems and cost-data makes it hard for the average researcher to provide this evidence. Fortunately, there are ways to overcome this issue. One could, for example, work together with companies that have access to this type of data. Just a matter of sending and e-mail and explain your ideas and needs to the right person I guess... ;)

Migration to the nine-headed monster

2009-03-22T12:30:00.005+01:00

After some recent activity on the psat-dev mailinglist I became aware of the (lack of) available builds for php-sat. Even though the development speed is not what I would want it to be (so much fun things to do, so little hours in a day!) I still believe it is important to release early and often.

Fortunately, Eelco Dolstra had some time to migrate php-front, php-sat and php-tools to Hydra, the new Nix-based continuous build system. After some tweaking we now again have access to unstable build for all PSAT-projects. Go Hydra!

[Trivia] generating eclipse project dependencies with maven2

2009-02-10T20:35:00.003+01:00

When we migrated to maven2 a few months back we had little problems, accept that we could not figure out how to automatically generate project dependencies for eclipse. Apparently, maven1 has a special tag for this, but this did not make it into maven2.

Recently, (and by that I mean a few weeks back, just didn't bother to post this yet) one of my co-workers found out that you can simple pass the location to your eclipse-workspace to the eclipse:eclipse tag:

mvn eclipse:eclipse -Declipse.workspace=/path/to/your/workspace

and we all lived happily ever after ...

Visualizing the PHP grammar

2008-12-16T20:37:00.007+01:00

A few weeks ago an e-mail from Didier Garcin popped up on the Stratego mailing list. He explained that he had written a python script that could visualize an abstract syntax signature. The script was also send to the list and I finally had some time to check it out.

It turned out that I had almost anything installed to use the script, only the pydot dependency needed some work. This was mostly because the script only seems to work with the 0.9.10 version of this library. After getting the script started it was really simple to generate the signature from the PHP-Front grammar.

So, here is the one for PHP4:

And the one for PHP5:

The first thing I notices where the big rectangles in both versions. These rectangles are the statements (smaller one) and expressions grouped together. What I also notices was that in both versions we see that the bottom of the graph (which corresponds with the smallest units in the language) looks the most complicated. This corresponds very well with the amount of effort put into the modeling of this part of the language.

Comparing both grammars to each other we can see that the latest versions is the most complicated one. Furthermore, if we compare both graphs to the graphs shown in this post we can see that the Java-graph appears to be the most similar one.

Actually, I do not think these images show anything, but please explain it to me when you think I just don't see it. Anyway, at least we have some nice pictures now :)

P.S. for those who are interested, more detailed images (in svg-format) are available here.

Shameless plug

2008-12-02T18:43:00.003+01:00

Instead of writing about the new and interesting stuff I am currently researching (mostly because the results still need to be processed a bit) I am only going to mention my the link to my new home on the web:

http://Eric.Bouwers.info

Now I only have to figure out how to get this blog into the same style ...

Another JFall

2008-11-12T20:27:00.003+01:00

Today I attended the JFall 2008. Another instance of the conference of the NL-JUG aimed at all the Java programmers in Holland. Since two of my colleagues got the last two tickets I had the pleasure of walking to the location with only one of them, the other one missed his train.

Anyhow, let us see what the day has given us.

Duane Nickull was the first speaker of the day. He shared his view on what web2.0 and SOA was. We saw many slides (with many boxes and arrows) explaining which entities play a role in these types of technologies. Unfortunately, his presentation was a little abstract, because I didn't notice any concrete examples (maybe I missed them though). On the other hand, his anecdotes were nice and interesting. The one that I liked the most was about a company that is trying to apply the open-source software development way of contributions to the making of movies. Deciding what is in a movie sure sounds fun to me, so there should be some kind of business model in there right?

The second talk I attended was given by Allister Smith and was titled "pragmatic Java". Hoping on a presentation full of pragmatic solutions for common problems, I was a bit disappointed when the talk compared Java to languages such as Phyton and PHP. An example program was given in Python and then redone in Java using the spring-framework. Naturally, the Java example was much more bloated. After this, an example of a Java implementation was given in which the typing was essentially stripped away (by using only Objects) and value-passing was done through Maps and Lists. The speaker had a good point in the sense that this can be just as quick and short as a scripting language, but using Java for this just feels wrong. It is an example of using a language because of the language, not because it has the features you need for a project.

The last talk before the lunch was an introduction to the Java Memory Model. Peter Veentjer (who seems to know a lot about these things) gave a nice tour around some of the pitfalls of Java concurrency. Although the talk was a little low level, it was really understandable. I do not have to deal with concurrency at the moment, but some of the pointers are good to keep in the back of your mind during development. Certainly a useful presentation.

Right after the lunch the evangelists of Sun gave the second keynote of the day. Normally I do not really like these kind of talks because they can feel like you are watching a long tv-commercial without seeing something useful. However, I was pleasantly surprised that the demo's showed some really nice stuff (besides being slick of course). It turns out that in the new version of JavaFX it is possible to drag applets from your browser to your desktop and still work! There must be some real-world usage scenario's for that I guess. Also, a demo was given of alternative ways to use your Wii-mote. Definitely a better talk then I had expected.

After the demo I was quick enough to sneak into the presentation of Huub van Thienen about closures in Java. I was lucky to have a seat because the room was really packed with people. Huub gave a really nice introduction into what closures are, and how they could be used in Java. His presentation showed the pros and cons without giving away his own opinion. Actually, he even promised a candy-bar for the person that could guess his opinion about the subject. I still do not know :(. Even though I knew most of the thing already (because of knowing Haskell), I think this was the best presentation of today.

As a last presentation I attended a Hands-on-lab about dealing with legacy code. Since we are usually analyzing legacy code for customers, I thought it would be nice to hear other peoples opinions about the subject. The set-up of the lab was really nice, first some explanation, then some coding, some more explanation and so on. Unfortunately, we ran out of time in the end, but it was still a nice experience. I also relearned one of my pitfalls during the session. When trying to fix a bug I tend to first figure out how to fix a problem, than actually fix it, and later on write a test for it. Usually, I also try to run the test without the fix to see whether it fails, but sometimes I forget. To counter this I should first write a test, and then fix the problem. However, sometimes it is too tempting to just fix the problem :)

All and all it was an interesting day. No real eye-openers, but certainly not a complete waste of time. On to the JSpring I would say!

Focussing on the problem

2008-11-05T21:30:00.000+01:00

After a solid month of being a part-time PhD I have gotten many tips (and comments) on kick-starting my project and doing research in general. Currently, my goal is getting a clear picture of the problem that I want to solve. I know that there is a problem (and I have a vague notion about how to describe it) but getting a clear definition is not something that comes easily.

On the other hand I am not afraid of spending time on finding the problem. When the problem is clear it is usually easy to think of scenario's that can solve it (although actually executing these scenario's might be tricky).

And focusing on getting the problem straight is also not bad for presentation purposes. Several of my colleagues (and other people as well) explained to me that during a presentation it is very important to explain the problem that you solve. Also, and this is something that I usually forget to think about, it is important to explain in which cases your solution is not going to work.

It does not matter that this might take up a big chunk of your time because most people probably do not (completely) understand your solution anyway. As long as they know which problem you have solved under which conditions, they are going to be happy. More details about how the solution works can always be read in a paper, or discussed over some beverages.

So, back to the literature study it is! By the way, if anybody has a nice suggestion to keep track of interesting research papers online, please let me know!

Finish what you start ....

2008-10-07T20:41:00.003+02:00

When I was young, my mother used to tell me that I should first finish what I started before moving to something new. I think this was mostly because in order to finish something I had to clean up the mess I made, but it's not a really bad rule to keep in mind I guess. However, even though I should first finish all my other projects before moving on, I picked up another project last week: getting a PhD.

Yep, as of the first of October my boss allows me to spend two days a week on doing research. This research is going to be (how surprisingly) in the field of static analysis and software quality. Our first research-topic is already starting to shape itself and I believe (how surprisingly) that it is going to lead to interesting results.

It might be nice to perform research, but in order to get a PhD you cannot get far without 1) good focus and 2) good supervisors. Luckily, I have a team of two supervisors that can certainly keep me focused: Joost Visser and Arie van Deursen.

In order to keep everybody up-to-date with the progress of the research, and to spend a little time in a more research-oriented environment, I will be traveling to Delft once a week. While last week was mostly filled with arranging a workspace, this week is going to be filled with giving a talk at the Research Colloquium. So if you have not heard my Fluent Interfaces talk yet, this is probably your last chance :)

A Java-Summercamp

2008-09-24T20:20:00.008+02:00

It has been a while , but on the 29th of August I have attended the 2008 version of the Java Summercamp. This gathering was organized by profict, a dutch IT-company. They have an office with a great view (picture), now that is what I call a green working environment!

The topic of this day was Domain Specific Languages (DSL's). Since my talk about fluent interfaces at the J-Spring 2008 I became more and more interested in this topic. I hoped to hear more about why you would want to use a DSL, and see some examples of DSL's in practice. Luckily, I got what I wanted.

The first speaker was Neal Ford. His first presentation (slides) gave a general overview of the usefulness of DSL's. He argued that Java can be seen as a framework-oriented language. Nowadays, a Java-programmer uses many frameworks which he ties together with configuration-files written in XML. He proposes to use a DSL to abstract over these large configuration files in order to make it easier to tie frameworks together. He also gave an overview of some techniques to implement (mostly internal) DSL's. Actually, his second presentation mostly consisted of examples of DSL's in various languages. It is always fun to see examples of what you can do in other languages.

Sven Efftinge was the second speaker with his presentation (slides) about XText. I was surprised to see that it actually looked very simple to 1) create a DSL by typing in EBNF 2) generate an eclipse editor for this DSL with the click of a button and 3) generate a generator for your DSL using the same click. Naturally, everything was already set-up so that it looked easier then it actually is. I have tried to make a small example to show at the office, but failed miserably to get the generator to do what I want. Anyhow, if you have a spare afternoon then checking out this project is certainly worth the effort.

The third (and last) speaker was Zef Hemel. His presentation (slides) about WebDsl gave a nice overview of the setup and current status of the project. I was already a bit familiar with the project and it was fun to get an update. Also, I enjoy seeing the face of people that are confronted with Stratego for the first time :)

All and all I can say that it certainly an afternoon well spent.

Is he back?

2008-08-10T11:41:00.005+02:00

It has been eight months since my last post to this blog. Also, the release plan did not work out as well as I had hoped. So what did I do in the intermediate months?

Well, I ended last year by buying me a 'real' house instead of renting an apartment. For us it is pretty large, currently even the cats have an own room, but this will probably change over time. Buying a house really helps you to spend your time since there is all sorts of paperwork to fill out, people to inform and things to pack. We moved in at the end of March and I think that we are currently at the point that every company we deal with knows that we had a change of address. The next objective is to unpack and store away everything that we moved. There are still some (closed) boxes standing around here and there.

During the time that we where preparing to move to our new house my (at that time) girlfriend and I where also organizing a very important event: our wedding. That is right, on April the 26th we got married! It was a wonderful day in which we did the things that we enjoy together with our friends and family. We got married, went to a movie and had a party at the home of our Scouts. Maybe not the most traditional wedding ever, but certainly one that we enjoyed!

Even during the buying of a house and the planning of a wedding one must keep on working, so I did. I learned a lot about how to do agile programming, how one can quantify the quality of software and how to be (even more) pragmatic.
Apart from the 'normal' work, me and one of my colleagues wrote a paper called Multidimensional Software Monitoring Applied to ERP. This paper is accepted at the SQM 2008. It was very nice to attend a conference as the author of a paper, certainly when the conference is held in Athens :)
Next to this paper, I also gave a talk at the J-Spring 2008, This talk, titled Putting Fluent Interfaces to the test, was about designing and using a Fluent Interface. If you are not familiar with this style of API-design be sure to follow the link.

So I bought a house, got married and enjoy the work that I do. I guess you van say I am really settling into society ;)

Unfortunately, this settling in has taken so much energy from me that I did not find the time to work on PHP-Sat. However, since I have found the time and energy to write this post, I should also be able to find some for the PHP-Sat-project again!

Calculating the complexity of PHP

2007-12-09T12:52:00.000+01:00

Not only is the question of calculating the cyclomatic complexity showing up in our mailinglist and bugtracker, it is also showing up on other mailing-lists! This shows that the time has come to introduce a solution to this problem based on PHP-Front:
php-cyco
(indeed, yet another creative name :)

This tool is added to the PHP-Tools project as of revision 421. The implementation is not very big, the code that does the actually work is about 20 lines, but it relies heavily on PHP-Front. Thats where libraries are for, right?

So what does it do? The tool basically counts the number of branches that exists in your code. This is done for the main-flow and separately for each function. By default, each function (and the main-flow) starts with a complexity of 1 since there is always a minimal path through the code. For each construct that introduces a branch within the control-flow, for example if-, for- and while-statements, the complexity is increased by 1. In the end the number represents the number of paths that exists from the start until the end of the function (or main-flow). The higher the number, the more difficult it becomes to understand and test the block of code.

The complete list of constructs that increase the complexity can be found at the bottom of the source. I think that the list is understandable, even though it uses 'Sorts'. If this is not the case please let me know, and I will put up a list using php-syntax.

As you can see the complexity is increased by logical operators. This is because the semantics of the code:

if($foo || $bar){ //code }

is equal to the following code:

if($foo) {  
  //code
} elseif($bar){ 
 //code 
}

in other words, we can rewrite a logical expression as a set of if-else-statements. Since they share the same semantics they should share the same complexity.

One last note, the tool actually calculates the minimum complexity of a function. Even though php-cyco is capable of including files, using the usual --*-inclusion flags, it might encounter situation in which it cannot resolve a filename. In this case the calculated complexity can be lower than the actual complexity because the included file could contain some of the complexity-increasing constructs.

So if you are curious to know which function within your php-project has the largest complexity I suggest you download the PHP-Tools project and start analyzing your code!

Please let me know if you have any comments or feedback.

[Trivia] Pentaho Mondrian Slow MDX Query

2007-11-29T21:47:00.000+01:00

Finally, another trivia-post. I could not find the answer easily on the web, but there might be people that are struggling with the same problem we had.

While working on my current project we ran into a problem with a MDX-query. In short, it retrieved about 14,000 rows from a database and displayed a subset of these rows on the screen in a variable ordering. The problem we where facing was that it took about 4-5 minutes before the data showed up.

We knew that the query was not completely trivial, but 14,000 rows is not that much data. Furthermore, one would expect that an OLAP-database could handle this kind of volume very easily. In the beginning we thought that it took so long because all of the data was first retrieved from the database and then sorted within the Java-code. On the other hand, sorting a list of 14,000 items should not take that long. An other theory we had was that the bottleneck was the number of queries that is generated (about 4000) to retrieve the 14,000 rows. This was not the case, every query only took 1-2 ms to complete.

So we fired up YourKit, a Java memory/CPU-profiler. I can highly recommend this tool to anyone who wants to profile there code. It provides detailed reports about all sorts of interesting things and comes with a nice interface.

While going to the profiling output we noticed that the code was spending about 50 percent of the time in a 'Sort'-method, and 40 percent of the time in a 'Debug'-method. Since we didn't see that much debug-output we did what any programmer would do when has not written the tool (s)he works with: we assumed that the profiler was wrong and concentrated on the 'Sort'-method.

Examining the profiler output some more we discovered that 40 percent of the time in the 'Sort'-method was actually spent by calling the 'Debug'-method above! So we looked up the code and found out that the people of Mondrian where actually calling this 'Debug'-method every time they compared two objects.

Question: When sorting 14,000 objects, how many lines of debug-output would you get?
Answer: A lot.

The funny thing was that we did see some debug-output, but not as much as you would expect from the code. Furthermore, the 'Debug'-method was only called when the log4J-level was set to DEBUG. We did use a log4j-configuration, the default that was shipped with the application, but this file did not mention Mondrian anywhere. It did mention a file called 'server.log' which we eventually found. The size of the log-file was about 1 gigabyte, which might explain where all the debug-lines went to.

Our current solution is to simply remove the log4j-configuration from our project. This still gives us enough feedback to track the usual things, but it also prevents Mondrian to go into debug-mode. It reduced the running time from 4-5 minutes to 4-5 seconds, a considerable speed-up don't you think?

The new release plan

2007-11-11T16:45:00.001+01:00

Last week I made a list of things that I wanted to do after reading Production OSS. Today I took the time to implement two of the items on the list, which reduces the list to only thirteen items. Luckily, the tasks on the list are not difficult to implement, but they do take some time to think about the best way to implement them.

The first thing on the list was bringing the website up to date. It still had some pointers to the build-farm in Utrecht and some tips to work around missing functionality that actually exists nowadays. I also tried to make it more clear what the intention of the project is, although I think it can still be made more explicit. Fortunately, this is also an item on the list :)

A second item on the list was the cause for a large number of mails from Jira send to the psat-commit-list. I made up a new release plan of PHP-Sat / PHP-front and also removed some issues/features that where no longer wanted. Let us take a look at the new milestones for the two main projects:

PHP-Front:
The 0.1 release must be capable of parsing, pretty-printing and reflection on PHP4 and PHP5 code. Furthermore, constant propagation need to be supported for procedural code without function calls. Within the 0.2 release this support is to be extended towards function calls and object creation. Support for more information about the environment of PHP, for example the types of internal functions, is planned for version 0.3.

PHP-Sat:
The release structure is closely related to that of PHP-Front. Within the 0.1 release it must support procedural code without function calls and object creation. These language constructs must be supported within release 0.2. The purpose of the 0.3 release is to add many new bug patterns.

In both projects we can see that the number of issues that need to be fixed before the first release is quit low. So hopefully we can make a first release around the end of the year!

So much interesting to read ...

2007-10-21T19:10:00.001+02:00

... and less time to do it!

Since I started my full-time job I noticed that it is a lot harder to stay up to date with all the latest (online) developments. During the writing of my thesis I had a considerable amount of time which I could spend on reading blogs and news-items, and following mailing-lists. When you spend most of your day actually working you learn to prioritize which things you want to read :)

One of the things I did managed to read, albeit a bit late, is this thread on the PHP.internals list written by Wietse Venema. It is a follow-up on this thread in which a first proposal was made to integrate a perl-style taint-mode into the core of PHP. The results posted in the follow-up thread look promising. It is also interesting to see that he has gone from a black-and-white taint-mode, to a more leveled approach. Currently the proposal only contains a subset of the levels available in PHP-Sat, but I think that the most fundamental ones are definitely there.

Even though Wietse is developing a prototype I think he will have a hard time getting this taint-mode into the actual core of PHP. Within both threads the general opinion seems to be that the idea is nice, but the developers of PHP seem to think of many situations in which it could fail. I hope to see more results of this idea soon!

Going over some other interesting threads in the internals-list I found a reference to a tool called PHPLint. (Isn't is funny to see that there are all sorts of initiatives popping up that that try to make PHP more secure/stricter). I haven't have time to take a better look at this tool, but a first glance definitely showed potential. I'll try to examine this tool more thoroughly at the end of this week.

While there is less time to read on-line material, there is more time to read off-line stuff. Since I am using public transportation to get to work I have an extra hour a day to read actual books and publications. One of the books I have read in the past few weeks is a printed version of "Producing Open Source Software" (ProducingOss) written by Karl Fogel. My conclusion: absolutely worth reading!

ProducingOss contains all sorts of tips, hints and best practices. Even if you are not involved in an open source project it is still useful to read. Almost everything in the book can also be applied to closed-source projects. Furthermore, it contains many pointers to other interesting literature. One of these pointers lead me to The Cathedral and the Bazaar, my current read-while-traveling-to-and-from-work book.

I intend to use several things from ProducingOSS within PHP-Sat. I will just have to think about how I can fit the project in my current schedule, but it will definitely be fitted in.

Attending J-Fall 2007

2007-10-12T20:50:00.001+02:00

This Thursday (October 10th) I was lucky enough to get a ticket (and approval) to go the J-Fall conference organized by the NL-jug. My conference day started when I met some colleagues at the train-station to travel to Bussum-zuid. Within this nice-looking town the J-Fall found its home in 't Spant, a professional conference-facility.

The keynote of the conference was given by the "Sun Java Technology Outreach Team", which is basically a group of four engineers that talk about what you can do with Java. The keynote started with a nice overview of the different technologies Sun is working on. After this, a demo of JavaFX was given. Chuck Munn-Lee showed how easy JavaFX makes it to create a circle that morphs into a rectangle when you click on it. I also liked the fact that his editor did not only support code-completion, but also 'Color-completion'. Unfortunately, the other demos were are a bit disappointing because of several technical problems.

The first 'real' talk I attended was called From Java to Ruby … and Back. The speaker provided lots of material on the slides which made them a little bit overwhelming. Fortunately, he assured us that the slides would also be distributed digitally. The contents of the presentation was an introduction to Ruby and a comparison with Java. One of the conclusions was that the speaker would happily code 80 percent of his applications in Ruby instead of Java. Quit a statement on a conference promoting the use of Java :)

The second talk I visited was about JUnit, or actually JUnit 4. I was a little bit disappointed by this presentation because all of the content was already discussed in an article printed in the last issue of the Java magazine. Furthermore, the pace of the presentation was terribly slow, which made it hard to focus. The only interesting bit of information I extracted was that JUnit4 allows you to define parameterized tests, something I might have missed in the article.

After a little bite, a longer walk and a stroll along the companies on display it was time for the second keynote. This keynote was very slick, had nice graphics and a strong story. Three different people talked about what Adobe offered, which activities are done by Adobe for the open source community, and what we can expect from Adobe in the future. They even tried to answer the question why Adobe was sponsoring the J-Fall. The answer was probably not very clear because I cannot reproduce it. The talk basically felt like one long commercial for the Adobe company.

Right after the second keynote I went to the talk of Peter Hendriks about Eclipse Mylyn. I very much enjoyed this presentation. The story was clear without telling to much detail and the demo was well-prepared. Peter even turned on the magnifying glass in Windows to zoom in to the interesting parts of the demo. These are the kind of details that show that this presentation was well-prepared.
On to the contents, the Eclipse Mylyn plug-in has all kind of nice features that can help you focus on your task. For example, the file-list can be filtered to show only those files that you have edited during the current task. Also, I especially liked the fact that you can define a test-target that only runs the tests associated with the current task. If you use Eclipse you should definitely take the time to check this plug-in out!

After getting another cup of coffee I set down in front of the biggest stage to listen to Java-specialist Heinz Kabutz. He explained The Secrets of Concurrency using ten (humorously named) laws. Each of the laws had an explanation of the name, a link to the actual problem and a solution. The talk was relatively straight-forward which made it easy to follow. A perfect talk for the late afternoon!

The last talk I visited was about the new JSR-286 specification for portals and portlets. Although the announcement implicated that the talk was only about the specification we hoped for a dynamic talk. Unfortunately, we got what was announce. An overview of the current version of the spec, a small list of shortcomings and a larger list of new features. Even though I was interested in the topic it was hard to stay focussed during the complete talk. Especially when the volume of the music in the bar next-door was turned up.

As a conclusion I can say that, despite some of the less entertaining talk, I really enjoyed the day. It was interesting to hear about a lot of different topics, and fun to see different companies present themselves. If I get the change I will definitely attend the upcoming J-Spring conference.

My last words ...

2007-09-28T11:28:00.000+02:00

... about my study that is!

After seven years of attending college I am no longer a student anymore. It still has to sink in a little bit, but I will probably get used to it very soon. It is quit confronting to transfer all of your (bank-)accounts to a non-student one :(

Thesis

I defended my thesis yesterday morning in front of a crowded room. Although I was a bit nervous before the talk this feeling faded away when I started the presentation. I thought it went reasonably well and this was confirmed by my supervisor(s). Please allow me to thank Johan Jeuring and Jurriaan Hage for their time and effort to supervise me.

If you are interested in the final result of the thesis you can visit my thesis page, or just download the complete thesis here. The slides of my presentation can be found on this page. Even though the project is finished (in the sense that I am not obligated to work on it anymore) I am still interested in remarks and comments you might have.

Work

And what do people usually do when they graduate college? Right, they take a vacation!

In my opinion I already had some vacation the past couple of weeks. I finished the major part of my thesis at the end of August, so in September I only had to integrate comments from my supervisors. This gave me lots of spare time which I used to relax a little bit.

Therefore, I took some time to found a nice job. After visiting several companies I decided to accept a job at the Software Improvement Group. During the interviews I got the feeling that this is a challenging job where I can learn a lot. Whether this feeling is correct is something that only time can tell us.
I will just wait and see what happens Monday morning!

A little migration helper

2007-09-01T16:47:00.000+02:00

You probably already heard about it, but support for PHP version 4 is partly dropped as of 31-12-2007. And after 08-08-2008 the support ends completely.

Luckily, the PHP documentation team provides you with a set of migration guides. Going through these guides can take some time, but it enables you to upgrade your code easily to be PHP5 compatible.

To make your life even easier, the PHP-tools project is extended with the tool test-migration. This tool performs some checks that are described by the migration guide to detect whether the code can be run under version 5 of PHP. These checks include:

Is there a function definition with the same name as a function newly defined in PHP5?
Is an object created without the class being defined first?
Where are the functions strrpos, strripos and ip2long used?
Is there any place in which there is reflection within PHP that uses changed behavior?

The first two checks are rather easy to understand, PHP5 will simply halt execution with an error when these issues are detected at runtime. Therefore, the warnings that are generated for these kind of patterns are shown with a 'serious'-level.
On the other hand, the last two checks do not find constructions that can halt execution. They detect places in which certain constructions are used. These constructions where already available within PHP version 4, but their behavior changed in version 5. To easily find these constructions they are flagged by a 'minor'-warning. More details about the changed behavior can be found here.

The first version of this tool is quit basic and performs only a few checks. If you would like to see more check included, don't hesitate to drop me an email or put them in the comments.

Finished coding (?)

2007-08-18T10:54:00.000+02:00

Monday was the day that I got back to working on my thesis. I spent the past few days coding and I think I am reasonably finished! The basics of the algorithm of the fourth phase are implemented, the GUI is updated with all kinds of small improvements and some documentation is written. The only coding that is left to do is making a solver for equations, a small todo compared to the overall work.

Now that the coding is done you might want to take a look at it. Unfortunately, the actual tool is not that nice to look at. Some people may like a command-line interface, but I guess most people prefer a graphical interface. Those that really want to run the tool from the command-line can do a checkout of the svn-repository, others can just visit the RFG web interface. There is some documentation available on using the interface, but you can always send an email to my gmail-acocunt with any questions. It would be great if you could just visit the test-page, make some exercises and send me some feedback about it.

I know that there are some things the in the GUI that can be improved, but I am mostly interested in whether the feedback helps you in solving the exercises. A correct step generates standard feedback which is not going to help you get to the answer. However, a step which contains an error triggers the algorithm of the third phase and gives more detailed feedback. Even though the feedback may be wrong sometimes, it is hopefully more useful than the message 'This step is incorrect'.

Experiencing a World Jamboree

2007-08-13T08:33:00.000+02:00

It has been one month since the last blog post. The reason for this is that I have traveled to England to (finally) attend the World Scout Jamboree. Describing everything that happened in the past weeks does not only result in an overly long post, it is also a bit boring. On the other hand, only giving the facts is also boring. Therefore, let us just scan through the trip and talk about the more interesting highlights.

Pre Jamboree Tour

Our trip started with a pre-jamboree tour organized by the our Contingent staff. We camped on Kibblestone, a reasonably big camp-site in England. Getting there involved two buses, a baggage-lorry and a boat. All the luggage of our troup, consisting of 40 persons, had to go with us on each of these vehicles. The boat was easy, but getting everything into the other three was a bit of a challenge. However, everything arrived safe and sound around 2 AM in the morning. After putting up the tents everybody slept like a baby.

The wheather

The first day of our stay in Kibblestone was accompanied by lots of sunshine. During my first meeting there where already complaints that some of the female participants had to put on more clothing when they walked around. Luckily for the complainer, this was forced down upon us by the weather-gods. It did not rain all the time, but it rain enough to turn the grass, the roads and the toilets into a big mud-pit. During the jamboree itself it was common to pull an item out of its storage place and see the original Kibblestone-mud still sitting on it. It was just everywhere!

Activities

The weather also influenced the activities we did. Most of the activities could also be done in the rain, in between two showers or indoors. Most of the participants enjoyed the numerous excursions, sport games (of all kinds) and campfires. For some of the participants the visit to Stratford-upon-Avon was a good excuse to buy all sorts of goods, including the new Harry Potter. Unfortunately for them they had to wait to get it because the first event in this town was a visit to the shakespearience. However, upon arriving in the right street it was quit clear that we would not be entering the theater. Between us and the theater was not the expected road, but a small river of about 30 centimeters deep. More time to shop, more time to start with Harry Potter!

Home Hospitality

An even more relaxing and special activity in the pre-jamboree tour was the home hospitality. The original concept was that each duo in our troop would stay with a family for two days. This was canceled by the English organization because there was a shortage of families that would host our scouts. Luckily, there where several scout-troops that wanted to host complete troops! After traveling for about six hours we arrived in Cardigan, a small city on the coast of Wales. We stayed wit the "3rd Cardigan Sea Scouts", a great group of people that terribly spoiled us. Our stay was a bit at the end of our pre-jamboree tour and the scouts of Cardigan made sure that we got our well-needed rest before we headed off to the real Jamboree. I cannot thank them enough for this fantastic time!

Surprising News?

On the last day of the pre-jamboree tour I finally spoiled a game that a part of our Contingent staff was playing for over a week. Each day, my girlfriend got one or two letters that together would form a sentence. Several people tried to work it out, but they all failed before I finally showed the answer to my girlfriend. For those of you that are curious, please visit the news-site of our troop on the 26th of July.

World Jamboree

It took a while before we left Kibblestone, one of the buses broke down after loading, but everybody of the Dutch contingent was on their way to the Jamboree. Some of the participants thought that there were a lot of people on Kibblestone (roughly 1350), they had not seen the Jamboree site yet. After only 3 hours on the bus we got out in the main bus terminal, only a short 20 minute walk from our campsite. I was told that many of our participants finally understood that taking to much luggage can really, really hurt your back.

Opening Ceremony

Even though the 20 minute walk showed a little bit of the size of the Jamboree, the opening ceremony did the rest. After 3,5 hours everybody was assembled into the arena, roughly 40.000 scouts from over 150 countries. During the opening ceremony, every country was welcomed by both a real and a digital flag. One can imagine that it took a while before every country was named.
The opening ceremony was to be held in the evening, around 8pm. This was changed once, twice and again because of a special agenda that needed to be respected. It turned out that Prince William himself was attending the opening ceremony. Our places in the arena give us a change of seeing him close by and even hitting him on the head, although nobody thought that would be wise.

Organization

Speaking of being wise, it was a good habit to pack as much as possible for a complete day. Walking to the other end of the campsite took about 45 minutes, that is without any chitchat-time. Furthermore, it could take some time to get you your food, a place to shower or a place on the bus. The shortest waiting time for a seat in the bus was about one hour, but it was not uncommon to wait for two or more. This showed that the English organization is pretty good in PR, everything was said to be completely organized, but not so good in actually making things happen. I still have to get a staff handbook which explains rules, procedures and activities for the Jamboree, something that could have been arranged a few months back. Furthermore, some of the activities themselves could have been prepared better. Sometimes even the people in charge of the activity did not know how things should be done.
Don't get me wrong, the majority of the activities were fun and exciting. Our participants and the staff had a great time! Everyone just expected the English organization to be more organized.

Scouting Sunrise

One of the biggest events during this World Jamboree was the Sunrise ceremony, held on the exact moment that the Scouts movement turned 100 years old. During the opening (and closing) ceremony the arena was filled with all sorts of different flags, during this ceremony everyone had the same Purple Scouts flag. Even though the ceremony was a bit too religious for my taste, I enjoyed the ceremony very much. Especially the moment that everybody was trying to collect 100 signatures on their sunrise scarf, 40.000 people wanting each others autograph is kind of cool to see. The rest of the day was filled with the food festival, each country on the sub camp prepared a dish typically for its country, sharing this with other countries. It was very nice to see so many cultures sharing their own ideas and rituals. This was truly one of the highlights of the Jamboree.

Departure

You might expect that the departure wasn't that well organized, but would you believe that the English organization began to think about the departure 3 days before the event ended? All of the previous arrangements with the Dutch Contingent where suspended which resulted in a rather huge challenge. In the original scenario we could stay on the Jamboree site until Thursday and Friday, but this was not possible anymore. After long debates ans short nights our Contingent staff provided a solution that was workable. The first group, including me, departed from the site on Wednesday to London for an excursion and from there to Essex University to sleep. It was very nice to sleep in a real bed and have access to your own shower! The next morning we started traveling around 6.00AM, I was home 14 hours later. The second group first had to relocate to a single spot on the Jamboree site after which they had a day of active excursions. They slept one more night on the Jamboree site and then had the same program as the first group.

Conclusion

I have not yet begun to tell everything that happened on the Jamboree. For more information about our contingent you can visit http://www.wj2007.scouting.nl/, for more information about the activities of the Jamboree you can visit http://eng.thejamboree.org/ when it is back up.

All there is left to say is that I had a great time at the Jamboree. Hopefully I will be able to join the 22nd World Jamboree in Sweden in 2011. Now lets get back to actually making sure I can actually graduate in October 2007 :)

Keeping it simpler

2007-07-13T08:51:00.000+02:00

It has been three months since I started writing about the third phase of my thesis. Given the fact that I thought it only needed some fine-tuning a few weeks ago, you might think that there is nothing new to write about it. If so, the next few paragraphs will proof you wrong.

During the development of the third phase I have worked with a set of test-cases which needed to pass in order to proof that the algorithm works on a reasonable level. When there where failing tests the algorithm was tweaked to let those tests pass. This resulted in putting heuristics in the algorithm until everything worked. Unfortunately, the heuristics seemed to work in practice, but where not always correct in theory. Even though I still believe that purity is not necessarily needed for the correct functioning of tools, it is needed in order to argue that an algorithm works.

So the first heuristic that was wrong was the introduction of meta-variables in the calculation of rewrite rules. Even though this works for a large number of cases, it also introduces dependencies which are not necessarily correct. For example, the rewrite rule between 1+1 and 2 would be A + A -> B. The LHS of this rule implies that the rule can only be matched a plus with two equal terms, creating a dependency that can easily be a coincidence. Therefore, the generated rewrite rules should not contain meta-variables, only 'normal' terms. This considerably simplifies the algorithm for rule-calculation and term-distance, while the results are still what is expected. So exit meta-variables.

The second heuristic that was introduced was the penalty given to guesses coming from recursion. I thought that this was needed in order to support the case in which a student applies a rule incorrectly, followed by a correct application of a different rule. Thinking about this a bit more I realized that it is impossible to support this situation. When two rules are applied and the first one is applied incorrectly, you can never know whether the second one is applied correctly from just looking at the terms. Therefore, a guess for either rule is can be a valid guess. So exit penalty.

Now that the algorithm is made even more simpler by removing the penalty there where 6 test-cases that still failed. In two of these cases the returned result is as good a guess as the expected result. The other four cases simply show the limitations of the algorithm.
In all four cases the expected outcome is the rule EqElem: A <-> B => (A /\ B) \/ (~A /\ ~B), but the actual outcome is ImpElem: A -> B => ~(A) \/ B. As you can see, the rules have a pretty similar LHS, the only difference is the operator, and a somewhat similar RHS. It turns out that as soon as the student makes a mistake with the priorities in applying the rule EqElem, for example by forgetting the parenthesis, the algorithm fails and returns the rule ImpElem as a result. This is because a change in priorities causes the AST of the RHS to be heavily transformed, which results in a large distance to the rule EqElem. This rule encodes a special priority in its RHS, creating a distance when this priority is not followed.

The conclusion that can be made from all this is that the algorithm of this phase can be kept simple, while still supporting a considerable amount of situations. For those situations for which it does not work, the problem is usually a (large) change in priorities. Luckily, these kind of errors are easily captured in rules for the fourth phase. So the battle might be lost, at least in the end the war is won.

Testing a contest

2007-07-04T20:08:00.000+02:00

Wow, that was a rather interesting experience. I spend the last three days on testing the ICFP-contest. There is not much I can say about the actual content of the contest, but I can say that I learned several new things. Some of them are not so funny, while others are very cool!

Anyway, lets just say that our solution was not exactly optimal :) I am sure that other will do better. So if you have not done so, register here.

Have fun and hack away.

It is getting noticed

2007-06-29T19:04:00.000+02:00

Within the last two weeks I noticed that PHP-Front and PHP-Sat are being discovered by people that are looking for PHP-specific solutions. It is not that we are flooded with request, but I am still happy with every question :)

The first question was send to the psat-dev-mailinglist and was about the Cyclomatic complexity of PHP code. I replied that it would not get into PHP-Sat because it is not a bug-pattern. However, it would be a nice tool for the PHP-Tools project. I made a similar tool for Java because of an assignment in the past, so it is probably just a matter of renaming the Strategies to use the PHP-Front api. Unfortunately, I didn't get an answer about how the report should look like. If you have any ideas please let me know in the comments, or in the issue.

A second question was about the grammar of PHP-Front, or actually the license of this grammar. The people behind TXL have derived a PHP-grammar for TXL from the SDF-grammar in PHP-Front. Since our license does not state anything about derived work without common source, we were asked for our permission to distribute this new grammar. Naturally, this permission was given very quickly and we were also allowed to take a peak at the source. I must say that I find it interesting, but I currently do not have time to look into it all. I imagine that the definitions of the grammars and TXL itself is similar to how things work in Stratego, but I have to look into that.

The last question in this series is about defined functions. Finding out which functions are defined in a project is easy when classes are ignored, a simple grep on the project will do. When a project also includes classes it becomes trickier to get all functions defined outside of a class. The question was whether PHP-Front could help with this issue, and the answer is of course yes!
Within the reflection part of the library the list of defined functions and classes is already available. This makes it possible to write a tool to show all defined functions in just a few lines of code. Since it was also a nice tool for the PHP-Tools project I added a tool for this last Friday.

Another issue that was brought up by the last e-mail is the issue of our implementation language. Since Stratego is relatively unknown the project has a steep learning curve. On the other hand, if I had chosen a different implementation language it would have taken me way longer to implement the current features. And besides, this piece of code is not that hard to understand right?

  defined-functions-main =
    include-files-complex
  ; get-php-environment
  ; get-functions
  ; if ?[]
    then !"No functions defined."
    else  map(transform-to-message)
        ; lines                    
    end

Where you at?

2007-06-20T22:41:00.000+02:00

Now that the propagation of safety-types seems to go smoothly it was time to dive into another subject: accessing the location of terms. In this case, the location of a term is defined as the location of the text in the original file that was parsed to that term. Since the strategy to annotate the AST with position-info is available in the standard libraries nowadays, it should be easy to access these locations and finally solve PSAT-91 right? Lets find out!

The first thing I did was to add a separate module to handle the low-level stuff of getting the location annotations. This module contains several getter-strategies that can retrieve, for example, the number of the start-line. The location info is captured in six different numbers: start-line, end-line, start-column, end-column, offset and length. A getter-strategy is available for all of them. Furthermore, the name of the file in which the term is defined can be retrieved.

Although these getter-strategies are useful, they are not meant to be called directly. I figured that the most common use of these functions would be reporting the values in some kind of (formatted) message. In order to capture this kind of behavior the strategy format-location-string(|message) is defined. This strategy takes a message with holes in the form of [STARTLINE] as parameter and fills these holes with values from the current term. A rather useful strategy if I say so myself.

To practice with this new piece of functionality I have added an extra option to the tool input-vector of the php-tools-project. This option allows the user to choose between the normal list, or the same list with line-numbers printed for each access. More information about this option and how to add an option yourself can be found here.

After this was done I moved to php-sat to make the output more concise. It was actually pretty easy to implement. The algorithm is nothing more then get-terms-with-annotations, make-nice-output. I actually spend more time on creating a test-setup for calling php-sat through a shell-script then on generating the more concise format. The only problem was that the adding of position-info everywhere interfered with the dynamic-rules. A few well-places rm-annotations where needed to fix this. Please let me know if you like the new output, or whether something should be added.

The next applications of the location info is the tracking of where untainted data enters an application. When a function is called with a parameter $foo which is tainted, it would be nice to show when it was tainted. I think this is not too difficult to add, but bugs always seem to lurk in 'I-think-it-is-easy-to-add'-features.

A last remark about locations is a small problem without an actual solution. Eventually php-sat must support function-calls. The algorithm to analyze function-calls is not complicated, but how can bug-patterns within a function be reported? A message before each call to this function? Within the file in which the function is defined? And what about cases in which one call is flagged and the other one isn't? And can we also handle object-creation in the same way? I haven't figured out how to handle this, so if you have any ideas please let me know.

Finetuning the third phase

2007-06-13T12:52:00.000+02:00

You might remember an earlier post about the algorithm for the third phase of generating feedback. This algorithm takes two terms and a set of (allowed) rewrite rules. After calculating the rewrite rule to transform the first term into the other, the algorithm chooses the rule from the set that is 'closest' to the calculated rewrite rule. This chosen rule can now be used to generate better feedback because it gives some insight in the intentions of the student.

In theory the algorithm functions quit well, and the same goes for the actual implementation. However, during the implementation of the algorithm I have run into a few details that needed to be fixed. This once again shows that theory and practice usually do not match completely :)
The following is a (small?) list of some of the refinements made during the implementation.

The rules(et)

One assumption that was made during the design of the algorithm is that rules must rewrite the current term into a term that is closer to the answer. For example, the rule A + B => B + A is correct from a mathematical point of view, but it does not help a student to get closer to an answer.
A second assumption that was made for the algorithm is that the ruleset is extended by combined rules. For example, the rules A => B and B => C are combined into a single rule A => C. The calculation of the combined rules is not very difficult, but getting the calculation to stop is a bit trickier.
The first experiment with rules from the domain of fractions went reasonably well, the only restriction that needed to be added was that restrictions on variables may not depend on themselves. So the restriction ... where B := B is not allowed.
The second experiment with rules from the domain of logic went into endless recursion, a clear sign of an additional problem. It turned out that rules where merging with themselves, resulting in an extra restriction to prevent this kind of behavior.

Calculating the rule

My first idea about the calculation of the rewrite-rule was a simple bottom-up traversal which returned a meta-variable as long as the (sub)-terms are equal. This naive algorithm worked reasonable during the first tests, but failed to perform well at larger examples. In these larger examples the calculated rule contained too much noise to see the important parts of the rewrite rule.
In an attempt to cut down the noise the algorithm was extended to find out whether a sub-tree of a rule can completely be removed. An example of this is the calculation of the rewrite rule between 4 + 5 + 2 and 4 + 6. The naive algorithm would give A + B + C => A + D as an answer. However, inspecting the terms gives the rule B + C => D as a more accurate match. This last rule still contains the same information, we have simply removed the noise of the A + .-sub-tree.

The first implementation of this extension only checked operators with an equal amount of children, and only with a left-to-right match. Even though this worked in some situations, it was still not good enough to be useful in general. Therefore, the matching part of the extension was improved by taken into account the associativity and commutativity of the operators. The different combinations of these properties either result in an exact-match (left-to-right), an assoc-match (left-to-Right, right-to-left) or an assocComm-match (all combinations of children are tried with an assoc-match).

Distance between rules

As with the calculation of the rules, the distance between the rules started with a naive algorithm covering several cases:

When we have two equal (sub)-trees we return a distance of 0.
When we have two nodes in the trees we compare the name of the nodes and all the children from left-to-right, adding distance when the two operators are not equal.
When either one of the trees is a leaf we check whether it is a meta-variable. If this is not the case we simple add a distance of 1 (for the leaf) and the size of the other (sub)-tree. If the leaf is a meta-variable we check whether it is a free variable, and return a distance of 0 if it is. Otherwise the same '1 + size (sub)-tree' is returned as distance. A variable is free when it is not previously bound by a match or a restriction.

Note that the above algorithm does not explain what should happen when two nodes have a different amount of children. After some testing I found out that it works quit well to just take the size of the extra children together with a penalty.

Another thing that is not considered in the above algorithm is the 'forgetting' of an operator. An example of this is the distance between the rule ~~A -> A and ~~A -> ~A. With the naive algorithm the distance between these rules can be quit large when the A in the rule is a large sub tree. In order to model this 'forgetting' the algorithm checks whether a node has a single child on one side. If this is the case the algorithm calculates the distance between the node with operator and the distance between the node without the operator. It then takes the smallest one of the two, taken into account some extra costs for adding the operator.

Putting it together

Now that all the sub-parts worked correctly the top-level algorithm needed to be implemented and tweaked. A first thing that was tweaked was the filtering of a list of matches. When more then one rule has the small distance, the algorithm first returned the first element of that list. Since this behavior makes the ordering of the rules important it needed to be changed. Now the algorithm takes the rule from the list in which the LHS of the rule is closest the current Previous Term.

Speaking of Previous Terms, the original Previous Term does also influence the choice for a rule. When we go into recursion by applying rules, the current PT changes. The changed PT matches better with rules that have a similar LHS, thus this LHS is different from the original PT. Assuming that students apply rules that at least partly match the LHS of a rule, we need to take the distance between the original PT and the LHS of the rule into account. Furthermore, we also take into account the number of rules that are applied to the PT in choosing a rule.

Does it work?

After all the tweaking and the bux-fixing the answer to this question is: Yes! You can take a look at some of the test-cases which list a PT, a CT and a desired result from the defined set of rules.
The tests-modules also include examples of situations which do not produce the correct result. This has to do with the fact that the virtual student made more then one mistake in the application of the rule. This shows that the algorithm does not work in all situations, but this was also not the goal of this algorithm. Luckily, the other examples show that the algorithm is capable of producing desirable output in a number of situations.

Some new features

2007-05-28T21:00:00.000+02:00

Last Friday, I had a conversation with nEUrOO in #stratego about the results he was having with php-sat (see his blog for more details). After the conversation, and after looking at the test-file he mentioned in his blog, I got started and added 2 new features to php-sat.

The first new feature is aimed at the usability of the tool itself, and is visible by a new command-line option: -ra CODE. This option accepts one of MCV, COR, EI, STY or OPT as input, and makes sure that the only analysis that is run is the one that belongs to the given code. In other words, you can now run, for example, only the correctness checks by calling php-sat with: --ra COR. This gives you a somewhat coarse-grained control over the behavior of the tool. A plan for more fine-grained control (on the level of patterns) is also mentioned some time ago, but the implementation of this level of control requires some more thoughts. In the meantime, please enjoy running a single kind of bug-patterns :).

A second new feature is added to the analysis of safety-levels. Consider the following example:

<?php
  echo addslashes(htmlentities($_GET['name']));
?>

The default configuration for echo requires a parameter to have both the level EscapedHTML as well as EscapedSlashes. Furthermore, the default configuration defines the return-type of the functions as:

function: addslashes       level: escaped-slashes
function: htmlentities     level: escaped-html

So this piece of code should not be flagged by php-sat. Unfortunately, previous revisions did flag this piece of code!

The problem here is that the analysis uses the safety-level of a function that is mentioned in the configuration file without considering the parameter of the function. This behavior works well for most functions, but when functions only add a property to their parameter it becomes incorrect. Because of this behavior, the echo-statement is flagged because the call to addslashes is only annotated with EscapedSlashes.

Fortunately, the solution is not that complicated. Since we know that there are several functions that add a certain property to their parameter, we add the possibility to specify this in the configuration file. The new syntax for functions that add a safety-level is a '+' after the level of the function. This '+' forces a function to inspect the level of its (only) parameter and combine this with the level that is specified as its safety-level. The combination of the levels is the result of the function call. (Small note: this behavior is (currently) only supported for functions with a single parameter.)

So from now on, when the following configuration is used:

function: addslashes       level: escaped-slashes +
function: htmlentities     level: escaped-html +

the example above is not flagged anymore because the call to addslashes is annotated with its own safety-level (EscapedSlashes), as well as the safety-level of its parameter (EscapedHTML). A pretty useful feature I would say.

A scouts week

2007-05-21T10:07:00.000+02:00

Those of you that (try to) read the posts of this blog every week might have noticed the two-week gap between this post and the previous one. This gap originates from the hobby I practice since I was a (very) little boy: Scouting. Within the past week I had the chance to go to two camps, with a three-day rest-period in between. This results in a large amount of dirty clothes, little sleep, a voice like a grinder and lots and lots of fun!

The first camp I attended was the 'clusterweekend' of the Dutch Contingent. My role in this camp was that of quartermaster of the Bontbekplevieren, one of the 25 troops visiting the World Jamboree this summer. Because it is almost impossible to get all of the Dutch participants together on one terrain, the 25 troops where divided into three clusters. There where eight troops in our cluster, each troop consisting of 40 persons. Adding a few people for camping staff, working staff and general staff we had about 350 people attending this camp.

Even though the weather forecast was a bit disappointing at first, the rain all fell down on us during the first night. This immediately showed that our new tents are water-proof, which is a good thing considering the normal weather conditions on England. During the rest of the weekend we played some games on the beach, sorted out a massive amount of badges, played in a casino and had a big party. Luckily, the sun was shining on Sunday so we could pack everything in dry conditions. The weekend was a great success, and of course there are some general photo's, as well as photo's of our troop.

When I came home on Sunday I quickly unpacked everything and washed some of the clothes. I worked a bit on Monday and Tuesday, but I also had to take care of some things for Ontmoeting, the second camp of this week. Ontmoeting is organized once a year for all the scouts of our region in the age of 11-15. They are mixed into sub-camps to compete for the first place. Each year the competition is wrapped into a certain theme, this years theme was 'Bond maakt het Bond'. The mission was to become the replacement of James Bond. The 153 participants where divided into 6 camps, each representing a 'superhero' of some kind. I was part of the Bassie en Adriaan-camp, a rather famous duo in the Netherlands.

This camp started on Wednesday with the packing of 'Diana', the trailer of our group. After loading all sorts of stuff we want to the campsite which was relatively small, but this made the whole thing kind of cosy. On Wednesday-evening we had a BBQ and a campfire with the staff, the children arrived on Thursday morning. The next three days where filled with all sorts of larger games, smaller games and some pretty cool ticket-activities. Naturally, you can check these out on some of the photo's, made by the same people that also made the camp-news-paper. It is always hard to tell about the whole camp in just a few words, but it all boils down to having a lot of fun. This year the games where really fun, thank you 'spelstaf', and our sub-camp has won the cup! To quote a famous clown: 'Alles is voor Bassie!'

These kind of weeks are a great way to relax, no worries about making deadlines or missing important stuff. It is simply not possible to read a real news-paper, so you just ignore the rest of the world for a couple of days. Also, it gives me a lot of energy to start working again, so let's get to it!

After catching some more sleep of course...

Merging fun

2007-05-09T20:41:00.000+02:00

Yesterday, commit number 379 and 380 introduced a renewed implementation of the constant-propagation, and new functionality for finding vulnerabilities. You guessed it, the merging of constant-propagation and vulnerability analysis has taken off! The cool things are that 1) the old tests all pass, 2) some new tests pass and 3) I get to write a lot more tests!

The main reason for starting the integration of both analysis was the fact that I saw a lot of code duplication popping up. This duplication was caused by the fact that the bookkeeping of internal structures is the same for all strategies, the code only differs for the properties of values.

With this last piece of information I started to merging. My first approach consisted of trying to pass a list of get-set strategies to the main-strategy and calling these strategies dynamically. This was obviously not a very good or nice start because it always seem to result in numerous segmentation faults.

Thinking about the problem made the second attempt somewhat more pragmatic. Instead of generalizing I just wanted to make it work for constant propagation in combination with a second analysis. So I rewrote the strategy to receive two strategies, one for getting the properties of literals and one for getting the properties of operators. The choice for these language constructs is based on the reasoning that these constructs are the only ones that make or manipulate the actual properties of values. The other language constructs manipulate the flow of the values instead of the actual values.

When this all seemed to work the more difficult challenge had to be solved, manipulation of variables and arrays. It turned out to be more simplistic then I thought because of the indirection between the variables and their values. For the purpose of dealing with aliasing, a variable does not point to a value but rather to a value-identifier. This identifier points to the actual value. This makes the creation of a reference easier, we just create a mapping from a variable to the value-identifier of the referenced variable. Because of this indirection we can simply make the value-identifier point to more then one property, implemented by a dynamic-rule for each property. This makes the merging of sets of dynamic rules a bit harder, but not impossible.

It might sound simple (or incomprehensible), but getting everything right was still a bit tricky. For example, when an assignment is made the property of the RHS must be known before the LHS can be assigned this property. So what happens when the constant propagation cannot compute a value, should we simply fail to assign a property?
The answer is no, the second analysis might still be successful. These kind of little problems made the implementation a little less straight-forward, and the code a little less beautiful.

However, the result of it all is that the following example is now flagged correctly:

<?php
 $foo = $_GET['asdf'];
 $bar = 1;
 $bar =& $foo;
 echo $bar;
?>

In this case, echo $bar will be flagged by the latest php-sat.

I experienced one problem with the implementation that is related to the semantics of Stratego. My first attempt in adding an annotation to a term was something like this:

 add-php-simple-value(|val):
    t{a*} -> t{annos}
      where  b*    :=  a*
           ; annos := [PHPSimpleValue(val) | b*]

This works perfectly, the annotations are matched as a list by the *-syntax, and a list is added as an annotation to the term again. The only problem with this is that the second time this rule is applied it matches the annotations as a list of a list of annotations, which was not the behavior I desired. This problem is easily solved by also adding a * to build the term:

 add-php-simple-value(|val):
    t{a*} -> t{annos*}
      where  b*     :=  a*
           ; annos* := [PHPSimpleValue(val) | b*]

Now the list of annotations is not wrapped in an actual list anymore. I know it is documented somewhere, but this little explanation might save some others from an headache or a long debug-session.

The next step in the analysis for vulnerabilities is a rather important one: testing. Even though the basic parts of variables and assignments are already tested, there exists a large number of scenarios that need to be tested on this new integration-strategy.
But hey, testing is fun!

Passing time

2007-05-01T14:52:00.000+02:00

After I stopped working on the GUI for the RFG I have been working in Haskell again. It has been quite a while since I have worked with this language, so it takes me some time to get used to it again. Since it is a strongly typed language, as apposed to both Stratego and PHP, some things take longer to implement, but some mistakes are found by the type-checker. Unfortunately, this means that I have not done anything terribly interesting for my thesis.

So lets look at the other interesting project, PHP-Sat. I have been working on the integration of a second analysis within the constant-prorogation. This is coming along nicely, but it requires some heavy thinking and careful considerations. I have already worked my way up to the expression-level, so I hope to finish the rest of the constructs that were already supported by the end of this weekend.

In order to tell at least one interesting thing, and to not waste your time completely, I wanted to point out some interesting video-presentations. The first one is also the first one I ever saw through the internet: Drupal, Joomla! & GSoC. The title explains why I wanted to see it, and it is interesting for anyone that wants to know more about the GSoc from a projects point of view. The second also comes from the Google Tech Talks and is called How Open Source Projects Survive Poisonous People (And You Can Too). It is given by the people behind subversion and I especially liked the story about the bikeshed. The third presentation comes from Bram Molenaar, the creator of VIM (yes, that is the editor I mostly use). He talks about 7 Habits For Effective Text Editing, be sure to check it out even if you do not use VIM.

The presentations mentioned above are (some of) the presentations I have already seen, the following are on my todo-list. Please let me know if anyone of them is super-great, or a total waste of time.

The paradox of choice
Education in the Digital Age
How to get paid to do open source (does this mention the GSoc?)

Doing it with javascript

2007-04-24T08:53:00.000+02:00

I have been working in the wondrous world of JavaScript the last couple of (work-)days, and I have to say that it kind of fun to work with. It turns out that the functionality that I want for the GUI is mostly captured in libraries, which makes it a lot easier to implement everything.

People that are interested in the current status of the GUI can always take a look here. Currently, the best way to view the page is through Firefox. I still have to do some debugging for other browsers, in particular Internet Explorer. I managed to get the designs the same across browsers by using the IE4linux project, but unfortunately the JavaScript-error-pop-up does not seem to work on my box. I am afraid I have to use a real Windows-installation for debugging this.

So what is the JavaScript suppose to provide in the interface? It enables the usage of the graphical view and the merged view. Without JavaScript the interface can still be used, but only through the text view. After the graphical view is enabled, the engine of Scriptaculous makes it possible to drag the keyboard to any position on the screen. I can recommend this library to anyone who wants to add nice animations to their website, it is easy to use and seems to work quite well. Scriptaculous builds upon the Prototype library which extends the objects of JavaScript with several handy properties. I have used some elements of Prototype in my own code as well, it is just to handy to ignore.

When the effects of the keyboard where finished, I started to search for a way to display mathematics and logic without to much effort. During my search I stumbled upon a library called jsMath which is capable of turning LaTeX-code into nice HTML. Even though the library is rather big, the fonts take up about 5MB, it is pretty easy to use. You can simple pass some LaTeX-code to a function which transforms it into HTML that can be shown in a normal website. The library seems to support most of the mathematical notation of LaTex, so I can at least use it for fractions, equations and logic.

The usage of jsMath is easy and attractive, but forcing a student to enter LaTeX-code is not my idea of a friendly user-interface. A normal Dutch student can understand the expression 2 / (3 * 5), but when it is written like \frac{2}{3 \times 5} it becomes harder to understand. So in order to allow a student to enter the expression in a normal notation, and view it in a nice graphical notation, I wanted to transform the first notation into the second one.

A (very naive) first approach involved splitting the string on the operators and putting the parts back together with the right notation. This works for very simple expression, but as soon as you want to have priorities and parenthesis it breaks. So the second approach needed to involve some kind of parsing.

It probably does not come as a surprise that finding a parser-generator for JavaScript is quit hard. There are some people that want it, but nobody which actually wrote one. The only thing I found was an example of an expression evaluator in JavaScript. This project has the elements that I want, but it has too much operators and fancy bits to be of immediate use in my project. Furthermore, it evaluates the expression, I want it to print LaTeX.

Even though I could not use the expression evaluator in the project, it served as a pretty good reference for the implementation of a more generic tokenizer and parser.
This generic code makes it easier to instantiate a parser for a specific domain, you only have to give information about operators and literals. Just like the expression evaluator it tokenizes the input string, after which it uses the shunting yard algorithm to transform the expression into an AST.
In this case the AST consists of objects holding other objects, which are clones of main objects. The objects need to be cloned to prevent infinite recursion to occur when the AST is printed (yes, something I found out the hard way).
I haven't had time to turn it into a library with a website, documentation and comments in the code, this is probably something for the future. However, I did have time to develop some tests for the code, long live jsUnit!

Another functionality that is currently available are the buttons on the keyboard. They work by adding text-snippets to the input field, so in theory you can enter an expression by only using the virtual keyboard. It took some time to figure out how to work with the Caret position, but after combining several JavaScript-snippets it seems to work well.

After reading all this you might wonder whether the GUI is done. The answer is no, there are still many things that can be done! First of all, the functionality needs to be debugged for IE and Safari. Second, when the text-view is hidden the keyboard does not function well. Third, using AJAX should make the updates go smoother. Lastly, it would be nice to be able to point to a place in the graphical view and place the caret at that position on the text-view. The first three todo's are definitely needed before the interface can be used for testing, the last one is a nice thing to have.

However, the real thing needed for testing the framework is .... the framework! It has been interesting to work on the interface with JavaScript and all, but it is not the core of my thesis. Therefore, the GUI is set aside. On to coding the framework!

The third phase

2007-04-15T17:15:00.000+02:00

In the beginning of this week I wrote down a description of the third phase of feedback generation. This phase has access to the previous term (PT), the current term (CT) and a set of rewrite rules. The rules describe valid actions on the domain, for example the adding of two fractions:

A/B  + C/B -> (A+C)/B.

In the case that the PT is 1/3 + 1/3, the CT obtained after application is 2/3.

So if this is the input, what is the output? You guessed (or read) it, a feedback-message! This feedback-message is supposed to contain more information then 'this is incorrect', but it can only use the CT, the PT and the allowed rules. Furthermore, the algorithm is assumed to only start when a mistake has been made.

A first try

When we know that a mistake has been made, we also know that there is no path of rule-application which leads from the PT to the CT, otherwise there is a rule which is not valid. In order to get a path between the two terms we introduce a magic rule R which exactly encodes the rewrite between the PT and the CT. In the case that the PT is 1/3 + 1/5 and the CT is 3/15, we have the following R in which A != B != C != D:

A/B + A/D -> B/C

Now lets assume that we have the following (conditional) rewrite-rules:

(1) A1/B1 + C1/B1 -> (A1 + C1)/B1  
(2) A2/B2 + C2/D2 -> (A2*D2)/(B2*D2) + (C2*B2)/(D2*B2)
(3) A3/B3 + C3/D3 -> ((A3*N) + C3)/D3 where N = D3/B3

Given this set, our task becomes to identify the rewrite-rule which the student wanted to apply, but in which he made a mistake. This can be translated into finding the allowed rule which is most similar to the R. We can use some form of tree-edit distance for this problem, since the rules actually represent a structured action.

There exists many different tree-edit distance algorithms, for this algorithm we can use a rather simple one. When we encounter two intermediate or leaves nodes which cannot be matched we replace the one with the other. This operation costs 2, one node is deleted and one node is added. When we encounter a leave node which needs to be matched against an intermediate node we check whether the leaf node is a free variable. A variable is free if there is no previous match and the variable is not subject of any restrictions. When the variable is free we simply match it against the sub-tree, otherwise we replace the variable with the sub-tree which costs 1 + size(inserted-tree).

To illustrate the distance we calculate the difference between (1) and R. Within the LHS we need to replace B1 with B which costs us 2. The rest of the variables can be matched against each other (so A = A!, etc). Within the RHS we need to replace A1+C1 with B which costs 3 + 1 = 4. This replacement needs to be done because B is already matched against B2 in the LHS. The last step is to replace the B1 with C in the RHS which costs 2. This has to be done because we already matched B1 to B in the LHS, and we know that B != C. This results in a total distance between R and (1) of 8. If we perform the same algorithm for the other rules we end up with distance(R,(2)) = 16, and distance(R,(3)) = 8.
Even though (1) and (3) have a similar score, we end up with rule (3) as our guess. This is because rule (1) cannot be applied to the PT, so it is more unlikely that this was the intention of the student.

Unfortunately, we are not done yet because the student could have taken a correct step before making a mistake. To model this we calculate a new set of PT's by applying the rules where possible. This results in two new PT's, PT1' = (1*5)/(3*5) + (1*3)/(5*3) and PT2' = ((1*5)+1)/5. Calculating the rules R1, R2 and all the distances we get six new distances. None of these distances is smaller then the distance of 8 we already have (the proof of this claim is left as an exercise for the reader), therefore we stop the recursion and return a feedback-message containing the rule (3) as a guess.

Although I knew we needed to tests this algorithm more thoroughly, it seemed to be correct to me. However, the assumption that the recursion can be stopped when there is no distance <= the lowest distance up until now can not be made out of the blue. This has to do with confluence, a property that is not guaranteed for the set of rewrite-rules. Sigh, just when I thought that I had a fitting key for the lock, I could not turn it to unlock the door.

Getting the facts

The concept of confluence came up Thursday and I have been trying to get around it until today. A first thing that I did was sum up some properties about the scope of the problem.

The terms are rather small (100 nodes or less)
There are few steps between the start and the answer (15 or less)
All rules are applied with a reason

The first two assumptions follow from the fact that teachers want students to practice the same routine with many different situations. The last one comes from the fact that students for example know that the denominator and the enumerator of a fraction may be multiplied by the same digit, but they do not do this at random. Such rules always have a context in which they are used. Therefore we can assume that the allowed rules always rewrite a term towards an answer.

With these assumptions in mind I noticed that the domain of fractions has only a few allowed rules. The same holds for the domain of equations and the domain of rewriting logic formulas to CNF, there are only 6 allowed rules for this last domain! Even if we combine rewrite-rules, by unifying the RHS of a rule with the LHS of another rule, we only get 9 rules for the domain of logic. These are not the kind of figures a computer cannot handle within a few milliseconds.

When we introduce new rules by unification this can be viewed as applying the rules after each other on the same (part of the) term. For example, if we unify the rules (2) and (1) from above we get:

1.2 A2/B2 + C2/D2 -> (A1+C1)/B1 
        where B1 = B2*D2, A1 = A2*D2
            , C1 = C2*B , B1 = D2*B2

If we perform the same algorithm as above, this rule surfaces as the result with a distance of only 4. The only right thing to do now is to return both rules (1) and (2) as a result. We cannot deduce which of the two rules went wrong, but we know that the error is somewhere along this path.

If we compare this with the first result of the algorithm we see that it is completely different. However, if we look at the example we see that it is indeed more likely that the student wanted to apply the rules (1) and (2). A guess which complies more with my intuition because of the matching denominators in the answer. Furthermore, this adapted version of the algorithm also work on the other examples that I tried, even the ones for the domain of rewriting logic!

The solution?

Now that the improved algorithm seems to work it would be nice if we can prove the claim 'we can stop when the distance becomes greater'. We can view the path between the PT and the CT as a sequence of allowed rule application in which there is an error. This error can be anywhere on the path. So is i is an allowed rule, we have something like i_n..i_m . error . i_k..i_j. The recursion in the algorithm strips of the first set of rules, so we end up with error . i_k..i_j.
Because we assume that all rules rewrite the term towards an answer we argue that stripping of allowed rules results in a smaller distance. When we 'jump over' the error the distance becomes bigger because we get strange R's which do not look like an allowed rewrite rule at all, otherwise we could have stripped of another rule.

When we combine this reasoning with the fact that we only have a small sequence of steps, I believe that this algorithm will at least give better feedback in many practical situations. Whenever it is not possible to make a good guess we can always fall back to a message like: 'We do not know what you did, can you try to do it in smaller steps?'. I don't see a problem here because the tools are focused on practicing a task in small steps. Now lets see what my supervisor thinks of it.

Thinking of Merging

2007-04-10T20:00:00.000+02:00

I have been dealing with some challenges in the last couple of days. For example my practical assignment for DBA, to be implemented in MIL, and styling the GUI for my thesis, which is coming along just fine I guess. Both of these tasks are easy for people who invented/work with it every day, but I sometimes find it hard to wrap my mind around the problem or keeping track of every detail. Good luck for me there exists a topic where I can work on without repeatedly searching on Google, analyzing PHP!

Speaking of analyzing PHP, Martin has written a blog about the generation of rules for operator-precedence in PHP. He mentions some interesting ideas for work on grammar engineering, so if you are looking for a (thesis)-project you should definitely check it out. Otherwise it is just an interesting post to read.

As for my work in operators in PHP, I have finished the rest of the operators in PHP-Sat. Furthermore, the implementation of the constant-propagation regarding operators is revised within PHP-Front. This is done because I am thinking about merging the constant-propagation and the safety-type analysis into one big analysis. I know, it sounds like premature optimization (a.k.a. the root of all evil), but I can explain why it is necessary.

Consider the following piece of code:

  $foo = array(1,2);
  $foo[] = $_GET['bar'];
  echo $foo[2];

When we consider the constant-propagation we first assign the values 1 and 2 to the first two indexes of the array. The value of $_GET['foo'] is then assigned to the third index of the array which is the parameter to echo in the last statement. We know that the value is assigned to the third index because PHP-Front keeps track of the internal index-count of arrays.
Now lets look at the safety-type analysis. We first assign the safety-type IntegerType to the first two indexes of the array. The safety-type of $_GET['foo'] is then assigned to the third index of the array which is the parameter to echo in the last statement. We know that the safety-type is assigned to the third index because PHP-Sat keeps track of the internal index-count of arrays.

You might have noticed that both paragraphs are almost identical, except for the kind of value that is assigned. Thinking about this case, cases for function calls and cases for objects it turns out that performing the safety-analysis involves a lot of bookkeeping. This bookkeeping, for example the internal index-count, is not specific for the propagated values, it encodes the internal semantics of PHP. Therefore, in order to provide a good safety-type analysis, we have to embed this bookkeeping.

In order to avoid code duplication, which might be worse then premature optimization, I believe we must merge the two analyzes together. By separating the assignment of values from the bookkeeping we can visit a node, perform the bookkeeping and then perform as much analyzes on the node as we want. The only thing needed is a list of strategies that encodes a single analysis on the node.

The idea might sound a bit vague, but while I was working on the operators I already saw some duplication creeping in. Some of the strategies for both analysis only differ on the strategies to fetch or add some value, a perfect change to generalize a bit I would say.

The operator type

2007-03-29T21:30:00.000+02:00

My first intention was to name this entry after one of these quotes about assumptions, because in the past week I found out (again) that they are totally correct.

Last Sunday I started to work on typing the operators of PHP. My first attempt was really basic, simply follow the documentation and everything will be alright. So I started with the arithmetic operators '+','-' and '*'. They all act the same on the type level in the sense that the result is always integer, unless there is a float involved. The next operator in line was division ('/') which always returns an float (according to the documentation). I finished off with the modulus operator which behavior turns out to be ...... not documented.

Since I want PHP-Sat to follow the semantics of PHP I needed to know the exact semantic of this operator in PHP. Naturally this is not hard to figure out because we simply run PHP on some test-data and use the function gettype. I wrote a little script with some lines like:

...
echo "Type of 5/2 = ", gettype(5/2), "<br />";
...

which is not only tedious, but also a complete violation of the DRY principle.

In order to comply with DRY I turned to the eval function of PHP. This function evaluates a string as PHP code and can actually return the result of a its computation! I used this function within a loop to dynamically calculate the result of applying an operator to different types. You can find the complete script here, but I will show the critical part here:

foreach($types2 as $key2 => $val2){
    $code   = 'return ' . $val1 .' '.$op.' '.$val2. ';' ;
    $result = eval($code);

    echo ''. gettype($result) . ' (' . showval($result)  . ') ';     
}

The foreach-loop resides within another foreach-loop looping through a copy of the array $types2. This gives us access to two different types and the current operator. These are combined within a string which is executed. We then extract the type and the result of the execution and display it.

Basically you just simply pass an array with types and a operator to the function and it will output the type and result of all possible combinations. I put the output of this script here, you can find the types and values that I used before the actual result. The first few sections contain most of the unary operators, the binary operators are organized in tables. Within the tables each row contains the first value given to the operator, each column is the second value. I apologize for for the ugly formatting, just trying to be a good programmer.

It was now a trivial task to read type(s) of the modulus operator from the table and be amazed. The result type is almost always an integer, but it can an also be a boolean type! This comes from the fact that whenever the RHS is a '0'-value the modulus cannot be calculated. Where other languages would simply halt execution, PHP returns a 'false'-value and issues a warning. This is also the case for division and is now also handled correctly in PHP-Sat.

You might wonder why I have chosen to test all of the operators instead of just the modulus. The first reason for this is that I could simply not resist the temptation, it was just to easy to add all the operators. The second reason was that the first run of the script also involved the testing of the division operator. According to the documentation it always always return a float, but the table tells us that it return either a float, a boolean or an integer! I might be able to see that the boolean return-value is not documented, it is almost certainly a mistake to divide by zero, but the documentation specifically states that division never returns an integer! Luckily (yes I believe it is a good thing), this problem is already mentioned by someone else and I hope it will be fixed before the year ends.

Back to PHP-Sat, the todo-list regarding operators has been heavily shortened. The only ones left are the assignment- and string-operators. The first group involve some dynamic rules which I want to implement when I am in a more awakened state-of-mind. For the second group I still have to figure out which safety-type is to be assigned when the safety-type of both side differ. I currently believe it should be the lowest safety-type, but please feel free to provide me with a counter-example that shows that this belief is wrong.

Interfacing Feedback

2007-03-21T14:20:00.000+01:00

My framework for feedback generation does not need a nice graphical user-interface. The input is simply a set of strings (current term, previous term and maybe some file names), and the output is also a string (the generated message). Since I am perfectly capable of using a command-line interface, why should I spend time on designing a fancy interface?

For one simple reason: Testing.

In order to know whether the feedback that is generated can actually be of use for students I am going to test the tools on real-life persons! This will not only give me a change to get out the lab and mingle with normal people, it will also provide useful feedback about the usability of the generated feedback. I intend to test the tools on students and teachers in a normal school setting, something which will probably result in nice anecdotes of system crashes, hanging computations and incomprehensible error-messages. Definitely something to look forward to :)

I thought that the easiest way of making sure that the tools can be tested everywhere is by providing a web-interface. No problems with installation or configuration, simply fire up the browser and lets start the fun.

Unfortunately, the choice for a web-application raises some other problems like different interpretations of web-standards and dealing with response time.
The first issue is a matter of using the standards and applying some hacks here and there. The last issue is (hopefully) solved by making use of AJAX (yes, my thesis is buzzword compliant). I haven't had the pleasure of programming with this technique so this is a nice opportunity.

A different issue with the design of a graphical interface is more personal. I am not that great in designing user interfaces. Most of the GUI's I have designed have the same design or are only input-output fields. It is not that this describes my GUI's, but I will probably not bring home any awards either. This is definitely something I want to learn.

Fortunately I love a challenge, so I intend to make a high-quality web-interface for my feedback generation framework. I have read several papers and books and I think that my current design is (theoretically) pretty good. It is rather minimalistic, gives visual indications for different zones and allows the users to adapt it to their personal taste.

Please feel free to comment on the design. After all, feedback is critical for learning ;)

Summer of Code 2007

2007-03-14T09:43:00.000+01:00

For those of you who are unaware of the occasion, today is the day that students can start sending in their applications for the Summer of Code 2007!

Another change for students to work on open-source solutions, get a t-shirt, gain experience in working with larger projects, get a t-shirt, and to get paid for doing this!

Oh yeah, did I mention you also get a cool T-shirt?

Unfortunately, I will not be able to join this year because of an other world-wide event, so your changes of getting accepted have just been increased :)
This year I will just try to promote the Summer of Code because I think it is a wonder full chance to do something useful and interesting.

And what better way to spread the word then with some flyer's! We (that is me and my girlfriend) have translated the flyer to Dutch, but it is also available in other languages.
Please mail/print/fax these to everyone who might or should be interested!

Taking precedence

2007-03-12T20:37:00.000+01:00

It has finally been done, PHP-Front has perfect operator precedence!

And why can this be written down as a fact? Because of the work of Martin! He has worked on the grammar-engineering-tools tool for generating SDF priorities. When I worked on them I ran into some problems because of the decisions that where made during the initial development (read: when the tools had to be finished yesterday). This resulted in a common format for PHP precedence rules that was neither YACC-like nor SDF-like. Martin has rewritten the tools to use most of SDF representation and this worked very good according to all the solved issues. The operator precedence is now encoded into PHP-Front as separate modules for both version 4 and version 5, both of them over 6k LOC.

The (technical) details about how these files are generated will probably make a long and interesting blog-post. Since Martin says it is hard to find such a subject, not to mention (again) that it is his work, who am I to take this subject away from him? Maybe he can find some time after preparing the LDTA-presentation for Thursday. I won't be able to make it, but if you are close to Delft you might want to sneak into the Research Colloqium. (If you do, please tape it!)

Besides bringing perfect precedence to PHP-Front, this work has also resulted in a new issue. It was not very hard to figure it out, I just misinterpreted the note in the documentation. So I immediately fixed it by removing a special case which did not have to exist, just to put the icing on the cake.

Downs and ups

2007-03-03T09:35:00.000+01:00

Some weeks are filled with good things, others with bad things. For me, the last week was filled with both. My parents celebrated there 30th wedding anniversary, my little brother turned 21 and my last remaining grandmother passed away. You can probably figure out yourself which ones are good and which one is bad.

So the schedule of this week was a bit out of balance because of these events. However, I still managed to get some work done. The analysis for constant-propagation and the one for the safety-levels now share the same structure. This will make it easier to generalize the analysis into a more generic framework, something which will reduce code duplication.

I have also finished my thesis proposal which means that I can now start the real graduation process. The official start date will be on March 5th, next Monday. This process is suppose to take 22 weeks, in this case until the 6th of August. Since there are some other events in between it will take some additional weeks. However, this schedule still allows me to graduate before first of September 2007, the start of the new academic year and the end of my 5th year.

Unfortunately, people keep telling me that the changes on keeping this schedule are pretty slim. Each year, only 1 or 2 students manage to graduate within 5 years, the minimal amount of time for this study. A nice challenge I would say :)

Oh, for those who are interested, my thesis proposal can be downloaded from this page. Please let me know if you have any questions/comments.

Phases in rewriting

2007-02-22T11:06:00.000+01:00

Now that my proposal is really coming along the exact details of the approach become more clear. I already have written down all the steps of the research and implementation, the only thing I need is a green light from my supervisor. When I get this I will put a link up to the full proposal. For those that cannot wait I have written a little explanation about the functionality of my thesis.

As explained before the subject of the thesis is to create a generic framework that can handle the generation of rule-feedback. An essential property of any generic framework is that it can be instantiated on a particular domain. In this case the instantiation will need a parser and a solver for a specific domain. This is not a real surprise since these objects are always needed when a tool is constructed. Furthermore, an equality module can be given to the framework. Such a module can be used to check two terms on semantic equality instead of syntactic equality. This is needed because in some cases a teacher would want to allow an answer to be either 3/2 or 6/4 as long as the students calculates it correctly. In other situations the answers may only consists of simplified terms, hence the equality may only succeed on the term 3/2.

After instantiation the framework is able to generate rule-feedback for a particular domain. This generation is done in four phases, each of them requiring more information and resources. Phases that need more input are of course able to generate better feedback. Notice that they 'are able to', they do not necessarily generate better feedback. The instantiated framework will give you a change for better feedback, but the default feedback will be on the same level as current tools. Thus it is a change on a gain, never a loss.

Phase zero is able to generate feedback with only the current term and the previous term. These two terms are always available since a student will have to take a step before rule-feedback can be generated. The algorithm of this phase will calculate the answer, e.g. the term a student has to supply as final result, of both terms and compare those. When these answers are equal a correct step has been taken, otherwise the student has done something wrong. The feedback generated in this phase is only 'correct' or 'incorrect' because we have no further information about the intentions of the student.

Within phase one the student will supply the rule he wanted to apply. The algorithm of this phase will check whether the rule was correctly applied and whether the rule was correct. The later is easily done by using the algorithm of phase zero. When this delivers an 'incorrect' the rule was wrong. Checking for a correct application is a matter of applying the rule to the previous term and checking the result against the current term. When these are syntactically equal the rule was applied correctly.
The feedback in this phase can let the student know in which area he made a mistake. Either a mistake in the rule itself or in the application. This will at least be more of a help to a student then a simple 'incorrect'.

The second phase needs more input from the programmer. A set of rewrite-rules defining the allowed actions of the domain will need to be defined as input. From this set the algorithms of this phase will 'guess' the rule a student wanted to apply. When an error has been made the feedback can contain hints about this rule and pointers to explanations or examples.

In the third and last phase the programmer can also supply a set of 'buggy'-rules. These rewrite-rules contain patterns of common misconceptions. By finding a path between the current and previous term with the allowed and buggy-rules the algorithm of this phase can identify a mistake with a high precision. The algorithm for this is well defined by Hennecke, a short English overview can be found here. Feedback from this phase can involve a specific explanation about the mistake, maybe accompanied by an example of a correct rule.

The explanation of the second phase mentions that the algorithm 'guesses' the rule. This 'guessing' is not completely worked out yet, it is actually a large part of the thesis. Algorithms for the other phases are already defined and only need to be implemented in a generic fashion. The result will be a practical implementation combined with formal research.
Everything a master thesis needs, right?

Results from a meeting

2007-02-18T21:20:00.000+01:00

Last Tuesday I went to Delft for a meeting with Martin after a long period of only communicating through email/IRC. Although these form of text-communication work fine a real-life meeting will make it easier to discuss things.

One of the subjects of the discussion was my paper for the STC. I already gave my presentation for this course, but finishing the paper was not an easy task for me. As you might have noticed it is quite a challenge for me to write a text in understandable English. When the text must also contain some formal definitions and clear examples the speed of my writings quickly degenerates. However, I still managed to put together a reasonable result. After we discussed which parts needed some modifications I improved the paper in the past couple of days. The result can be found at the new talks-and-paper-page on php-sat.org. Please feel free to provide constructive feedback.
When you followed the link you might have also seen the new page for the PHP-Tools package. This package is now also build within the build-farm, thank you Martin, and available for download. If you have a cool idea for a tool please let me know via the bug-tracker.
Other topics that we discussed will help to improve the path-strategies for file-inclusion, improving the SDF-definition for HereDoc, develop more concise error-reporting and generating the priorities for precedence from the YACC-definition. I have worked a little on all of these issues in the last two weeks, but now I have better ideas to handle the problems I ran into.

A last topic of discussion was an idea I had for an algorithm to use in my thesis. This algorithm uses a set of allowed rewrite rules to ``guess'' the rule a student wanted to apply. I already wrote an example-scenario for my proposal, which is coming along great by the way, so after I reread this I will discuss it in a blog. I'll keep you posted.

Including only once

2007-02-10T15:39:00.000+01:00

This week I finally got around to the implementation of a strategy that combines constant-prorogation and some sort of type-state. It was a bit tricky to get it completely right, resulting in some very weird behavior during testing. Fortunately, the problem has been solved and the result is pretty good!

So what problem does this strategy solve? In order to explain this we will first take a quick look at how constant propagation is being handled within PHP-Front (and other Stratego-libraries).

When a value of a variable is known, for example when it is defined in an expression like $foo = 5, PHP-Front will add a dynamic rule rewriting the variable to the known value. This dynamic rule can later be used to retrieve the value, for example in the expression $bar = $foo+1. This last expression will then be rewritten to $bar = 5+1 which can be completely calculated again.

Using dynamic rules for linear code is easy, but when code branches it becomes a little bit more complicated. Take this example code:

   $foo = 'say';
  if($val){ 
      $bar = 'hello';
  } else {
      $bar = 'world'; 
  }

The value of $bar can not be statically determined, but we want to keep the knowledge about the variable $foo. A valid way to do this is to take the intersection of the two sets of dynamic rules, the normal one and the one after evaluating the if-branch. This will keep all information about variables that are not used, or given the same value, within the branches of the if.
If you want to know more about dynamic rules and constant propagation I suggest you take a look at this paper.

Besides the information about the constant propagation we need to take a look at the inclusion mechanism of PHP. You might be aware of the fact that PHP offers both an include as well as an include_once construct. The first one will always include a file, the latter one will only include a file when it wasn't included before.

Dealing with files that are always included in combination with constant propagation is rather easy. We just retrieve/parse/evaluate the file during the constant propagation. Dealing with files that are only included once is also easy with linear code, but things get tricky when branching is involved. Take this piece of code for example:


  if($val){
    include_once 'foo.php';
  } else { 
    //other things
  }
   //some code
    include_once 'foo.php';

Within the if-branch the file foo.php might be included and introduce some dynamic-rules. The code for the if will handle this probably so that is not a problem.

But what must we do when we arrive at the other include_once-construct for the same file? Well, there are three different scenario's that can occur:

File has not been included
File might have been included
File is definitely included

The first and last one are easy, just include the file or not, the second one is more complicated with respect to dynamic rules. We will again have to take the intersection of the current set of dynamic rules and the set of dynamic rules after inclusion of the file. This will make sure that we only keep the rules that will be the same in both cases.
Notice that we will have to keep track of the inclusion-state of every file. This can (and is) implemented as a state for a file, again with dynamic rules.

Implementing both of these solutions with dynamic rules separately is not that difficult, there are enough sources to figure things out. However, combining these approaches is completely trivial because you will have to deal with dynamic rule-sets and all sorts of merge-strategies. Fortunately for you this is all done behind the scenes. Please enjoy the better constant propagation as of revision 332.

Thesis subject

2007-02-05T23:01:00.000+01:00

Working on PHP-Sat this weekend got me a response on Sunday-evening in #stratego. I was told that it was nice to see some more progress on PHP-Sat again. It's very nice to receive such feedback!

What this comment also expressed is that the past month the actual progress on PHP-Sat was not really visible. I have mostly been working on the website and on the GrammarEngineeringTools. Two things that will improve PHP-Sat, but not directly.

But I have to admit, there was another activity that quickly filled up my time:
My thesis-proposal.

I have mentioned before that the subject of my thesis is interesting (of course!), but didn't not explain what it is about. So here is the short version of the goal:
By combining techniques from the field of term-rewriting, strategies and generic programming we aim at supplying a generic framework that supports the generation of rule-feedback with minimal effort.

After reading this, the first question would probably be 'what is rule-feedback?'
Well, imagine a tool that allows you to solve a mathematical exercise such as:
1/2 + 2*(4/5)
by rewriting the expression in little steps. So the first rewrite would evaluate the multiplication which result in:
1/2+8/5.
The second rewrite will perform the addition and will lead to the answer of:
21/10.
(Notice that the rules I applied here are actually a set of combined rules, adding two fractions with different denominator takes more then one step.)

When the application of a rule is incorrect, for example the answer 9/5 for the expression above, feedback will need to be provided. Useful feedback would help a student to understand the mistake that has been made. In this case it could be something like:
You have added two fractions without considering the denominators. Remember that fractions can only be added when the denominators are equal!

I have done quite a bit of research on the feedback that is currently given in educational tools. The conclusion is that it can definitely be improved and certainly needs to be made easier to define. By supplying a generic framework the task of implementing a complete tool is simplified into the specification of the domain.

How this specification can be done, and more details on how the generation of feedback will work, will be explained in some later blogs. I just wanted to let you know what I was doing all day :)

Visiting Dublin

2007-01-29T10:45:00.000+01:00

My girlfriend and I went to Dublin this weekend and we had a great time. We flew with Aer Lingus and stayed at the Jacobs inn. This hostel really relaxed and I can certainly recommend it to anyone who just wants to sleep low budget. We basically did some sightseeing and walked around town. On Saturday we went to Radio City Dublin to see the Heideroosjes, the coolest punk-band I know.

Radio City is a cozy basement with a bar, a stage and room for about 200 people. It looks professional, but they could improve the information flow about who is going to play when. When we asked which bands played that evening it took about 10 minutes and 4 people to tell us that they didn't have a clue. It all worked out fine though. Seeing the Heideroosjes in a place with only 20 people, half of them Dutch, was a bit weird, but they definitely rocked! We plan to see them again in the Melkweg on the 16th of March, hopefully with a bigger crowd :)

The weekend in Dublin has given me some time to think about the things I want to do this year. I have made up a little list of the most important things that I want to pursuit this year, a kind of (very late) New Year's Resolutions:

Finishing my Master Thesis
Getting a fun job
Improving/promoting PHP-Sat
Having an awesome World Jamboree
Climbing a grade 6a-route

These goals are not very surprising, but they require some shift in my priorities. Let's see if I can be part of the 46% that keeps such resolutions after 6 month. I personally think that the last one will be the hardest one to keep :)

PHP-Sat.org finished

2007-01-24T22:17:00.000+01:00

It took me a ((very) long) time, but I finally finished all the texts for PHP-Sat.org. It is always a challenge to think of the right subjects and placement of texts for a website, but I believe that everything is in the right place now.

The website contains all the basic things a project need: general information, source repository, mailing-lists and bug-tracker. The current information is quit basic, but it will grow over time.

But the website also contains some extensive documentation on the following topics:

This is also the reason it took some time to finish the site, but I think that it was useful. It gave me a a change to think about several aspects of the project.

Please let me know if you find any (spelling)-mistakes in the texts, still practicing my English over here.

PHP Operator precedence

2007-01-13T21:02:00.000+01:00

If you take a look in the PHP-manual regarding operator precedence you will find the following quote:

Although ! has a higher precedence than =, PHP will still allow expressions similar to the following: if (!$a = foo()), in which case the return value of foo() is put into $a.

This is not very informative, which expressions are similar to this expression?

The answer to this can be found in this (huge!) file. This file is made with a tool called 'generate-prec-rules', which was created this week. It does exactly what the name implies, it generates the precedence rules given a set of common-precedence rules. The file above is created with the precedence rules from the yacc-definition of PHP version 5.

But how can we interpret these rules? Let's take a look at an example rule:


context-free priorities
  "@" Expr -> Expr 
  <1> >
  Expr "/" Expr -> Expr

This rule disallows a "/" on the second position of the '@'. Please note that this notation also counts the string-literal.

However, the expression @ 4 / 5 is not invalid, it can still be parsed and evaluated. The rule above just explains how PHP places the parenthesizes in the expression, in this case like this:
(@ 4 ) / 5.
Take a minute to think about the expression and how it is influenced by the above rule, it took me a while to figure it out.

It is nice to have all of the rules, they describe the operator precedence very precisely, but the size of the file is a bit problematic. Every operator, there are about 32, gets a rule for each other operator for each expression it has. The '*' alone already occurs in 82 rules.

So the next step that we will have to take is to combine rules without changing the semantics of the precedence relations. An example of this is the combination of these two rules:


context-free priorities
  Expr "*" Expr -> Expr 
  <2> >
  Expr "+" Expr -> Expr  

context-free priorities
   Expr "*" Expr  -> Expr 
   <0> >
   Expr "+" Expr  -> Expr

into this rule:


     Expr "*" Expr -> Expr 
 >  Expr "+" Expr  -> Expr

Which means the same, but is a bit more compact and probably more understandable.

So when this tool is created, and some things are changed within SDF, we can incorporate the newly generated precedence rules into PHP-Front. This will solve some parsing problems and will give us an even better SDF-grammar for PHP. We will also try to generate a more understandable, one page list of the operator precedence within PHP to replace the quote in the current PHP-documentation.

A nice example of 'research meets real life' don't you think?

[Trivia] migrating ssh keys windows -> linux

2007-01-04T18:26:00.000+01:00

I can almost hear you thinking: 'what is this [Trivia]-thingie, we had labels right?' You are absolutely right! I just wanted to add a more visual tag to posts that contain trivia things. If you see the [Trivia]-thingie you can safely assume that the blog contains a short solution to a random problem. I am writing it down for several reasons:

I could not find the solution in a quick way

When I have the same problem I can find out what I did to solve it

When you have the same problem you can find out what I did to solve it

Enjoy!

I was migrating my SSH-keys from Windows to Linux and found out that my pass phrase was not accepted anymore. The keys would load into Pageant with the same pass phrase, but keychain would not accept the same pass phrase. I found this suggestion, but it would not work. Another suggestion was made here and this lead me to the actual solution.

The key to the solution (pun indented) was that the key generated under windows was not in the OpenSSH format. It is quite easy to convert it to the right format using puttygen and it worked after the conversion.

So if the key that you generated on windows will not accept your pass phrase on linux, convert the key to OpenSSH and try again.

Pimping my environment(s)

2006-12-30T11:53:00.000+01:00

You probably already noticed that the blog has been pimped. I have adopted the quote that was mentioned at the SUD, updated the links, added the logo and an overview of all the labels. The blog now represents more of what it already was, a place to write about the projects I am involved in. And yes, me is also a project I am involved in :)

Apart from the blog I also updated the PHP-Sat website. There is now some documentation for PHP-Sat and the bug-patterns. The documentation of PHP-Front will also be updated soon. The last thing I have to do is writing the friendly and catchy welcome page, always a difficult task.

We are traveling further away from the project when I tell you that I also updated my computer configuration. You might recall that I used to work on a virtual machine, which tend to be a bit slow. So my current configuration is a dual-boot system with Windows2000 and Fedora Core 6 (default).
The documentation for setting up the working environment was more or less a guide for myself to get everything working again. It was definitely worth the work of backing-up all my configurations. A complete compilation of PHP-Front and PHP-Sat now takes 10m47s instead of the old 23m37s.

The last environment that I have pimped has nothing to do with any of the projects, except the me-project. I have cleaned my room and moved some stuff around. It is surprising to see how many useless things I had and how much space you gain when you throw them out. Although I am one of those people that believes in: 'everything you throw away will be useful the next day, my trust in this claim is fading away. It has been two days now and I still do not need the four, 10 centimeters long, lightsabers collected from cereal-breakfast-boxes.

String representations

2006-12-22T18:06:00.000+01:00

With revision 299 we (again) have a list representation for DoubleQuoted- and HereDoc-strings. So the string "hello \t world" is represented by:


  ConstantEncapsedString(
         DoubleQuoted([Literal("hello ")
                                           ,Escape(116)
                                           ,Literal(" world")]
      ))

This not completely new because the first implementation already had this, but this representation had some problems. There was no way to model a hexadecimal escape without making things ambiguous. This problem can be solved by making the order of the internal parts explicit, but we then had a terrible representation of the string:


  ConstantEncapsedString(
       DoubleQuoted(
              DQContent(Some("hello ")
                                       ,Escape(116)
                                           ,Some(" world"))
     ))

Note that this string is represented with 1 of those DQContent-thingies, the biggest one has three children. So every string with more then 3 parts has nested DQContents. Let me give you an example, the string "Hello \\\0123" looks like:


  ConstantEncapsedString(
          DoubleQuoted(
            DQContent(Some("Hello ")
                                      ,DQContent(Escape(92)
                                                                   ,None
                                                                   ,OctaChar(48,49,50))
                                      ,Some("3"))
       ))

Terribly right?

So this had to be solved by a post-processing step. We have to walk over the tree bottom-up to rewrite these nasty DQContent's to a nice list. It is not nice to have such a post-process-step, but this was already required because of HereDoc-strings.

The problem with the HereDoc is analogous with the problem of the Dangling-else. If you have multiple HereDoc-strings with the same label you will have to choice where the first HereDoc ends. PHP always takes the shortest HereDoc so this piece of code has two variables:


<?php
    $foo = <<<BAR
       foo...
  
BAR;
  
    $bar = <<<BAR
       bar
  
BAR;
?>

As long as HereDoc is ambiguous this is easily solved by choosing the right amb-node.

But after the rewrite to the new internal implementation, HereDoc became unambiguous! This is a bit frustrating because it takes the longest HereDoc, which is wrong. I spend some time in trying to get it right, but I could not make it work (yet). So a new puzzle has entered the project, happy christmas! :)

P.S. As said in the last blog, I can hope, but maybe I should just read.

What's the deal with ... ?

2006-12-19T19:29:00.000+01:00

What's the deal with the lack of updating of PHP-Sat?
The last few weeks were filled with all sorts of other interesting activities, at least for me. My days are mostly filled with doing research for my master thesis and writing my proposal. In the past two weeks my free time was filled with the SUD, the visit to Google and the Grammar Engineering Tools. So plenty of projects, but little time to work on PHP-Sat.

What's the deal with this thesis then?
The thesis is the final project/course I will have to finish before I graduate. I will do some research to validate a certain algorithm that will improve feedback in educational programs. A more detailed explanation of the subject/algorithm/approach will be put into a blog soon. It's a totally different subject, but still interesting for people in computer science as in education.

What's the deal with this Grammar Engineering Tools project?
As mentioned before, the paper that was the result of the project was already submitted. Some improvements are made and the tools are (going to be) updated. My work on this project was still in the interest of PHP-Sat though. We have gotten a great insight in which combinations of operators are valid and which are not. This information will be put on the web as soon as we have a reasonable format for it, so stay tuned!

What's the deal with those labels/link underneath the posts?
The new version of blogger allows you to have labels under a blog. I thought is would be nice to order the posts according to certain topics. People that only want to read about my thesis can look here, those that only want to read about PHP-Sat here. I hope that the people behind blogger will add a RSS-feed per label in the future, but I can only hope :)

Operator precedence

2006-12-13T22:13:00.000+01:00

So what was the curious remark in the last blog? What is the interesting functionality that I have made? The title gives the area of the functionality away, 'Operator precedence'.

The problem with PHP, and most grammars in general, is that the operator precedence is usually ill-documented. There is some documentation in a table, but the real reference is the implementation itself. Martin has a really nice idea about how you can check two grammars on having the same operator precedence, simple yet elegant.
If you take two definitions of a grammar, for example one defined in YACC and one defined in SDF, you can extract what is allowed and what not. The process of extracting the precedence rules that encode the behavior from these formalisms is written down in the paper that is produced, but I am not sure whether or not this is put on the web before we know if it is accepted to LDTA 2007. I do not even know if I can explain this very clearly in one post. So I can not provide a link to the paper, but this might be an interesting subject to blog about for Martin. (Yes, this is a hint!)
After extracting the precedence-rules you have to rename constructs and filter extensions from the rules. Finding the exact rewrites that are necessary is easy if you first extract the production-rules that are possible. This reduces the set that you are looking at from 3000-5000 to 30-50 rules, which is much easier to examine. After the rewriting you can compare the two sets of precedence-rules by a simple diff, a built-in strategy.

So what did I do exactly? Well, I worked on the actual tools in order to get some result, and we definitely did! We found several (precedence) problems in C-Transformers and the SDF-library, which both target C. This demonstrates the great power of the tools, because I am not that familiar with C myself!

We also found some precedence problems in the PHC, which were fixed very shortly after the report was send in. I was aware of the fact that there are some problems in PHP-front regarding operator precedence. In fact, it was one of the reasons for making these tools. The number of about 400 precedence problems was a still bit overwhelming at first. But most of these problems are due to the same operators and just produce about 49 warnings because all of the other operators report an error on it. We still have a lot of work to do, but we now have tool-support for checking the precedence rules!

Back from Dublin

2006-12-08T15:11:00.000+01:00

The trip to Dublin can only be subscribed as really great. My dad and I had a great time and I can really recommend it to everyone to visit this divers city.

We took an Aer Lingus flight from Amsterdam to Dublin and where only 30 minutes late, but this is something you get used to when you use the public transportation in Holland. The cab that we took drove straight through Dublin, the city is really huge! Traffic all over the place (on the wrong side of the road), almost no bikers and crowded streets. After we checked in we spend the afternoon walking around the main streets of Dublin and I went to Trinity to meet Edsko.

There seemed to be some confusion about the time of the meeting, but eventually Edsko and John showed up so we could get something to eat at the Mona Lisa. The food and the conversation was really nice. We talked about parsing PHP, the differences between the internal representations and living in Dublin. We concluded that the projects are not really compatible because the internal representations are really different. These internal representations of the PHP-sources can be made compatible from PHP-Sat to PHC, but not the other way around. The goals of the projects are also quit different, but we could probably learn something from each other. Although this conclusion is a bit of a disappointment I had a really nice time. Edsko also showed me some of the inside of Trinity College, which is definitely worth a visit. Thank you Edsko and John for a fun evening, I hope we meet again sometime.

The visit to Google was on Tuesday at 12 o'clock, so we still had to fill the morning with something useful. We visited to the national gallery which had an interesting exposition about the Irish culture in the last 200 years. They also have a (very large) collection of other paintings which were less interesting to me, but my dad seemed to like them.

And then it was finally time to go to the Google Office. Leslie could not make it because she was sick, but Rob Holland was kind enough to take over the coordination. We started the visit in the game-room which is filled with video-games, a snooker-table and a massage chair. We left our bags there and Rob showed us around the floor and the different teams. Everybody seemed to be busy, but they also took the time to say 'hi'.
After the tour we went downstairs to the restaurant. There was plenty of food (all free), drinks (all free) and ice-cream (again all free). The conversation with the engineers during lunch was very interesting. They have done some fun (and dangerous) experiments with various (expensive) toys, but they also work very hard.
We finished the visit with the lightning presentations of our projects. The topics of the projects were pretty far apart, but it is good to broaden your horizon.
The visit confirmed my expectations that working at Google is pretty cool, but you will still have to work hard. This is not so bad because the people seem to be very nice and intelligent and the atmosphere is great. Thank you Google for making this visit possible!

We flew back on Wednesday after visiting the Guinness-brewery, you just have to visit this brewery when you are in Dublin.

The overall conclusion is that the trip was fun, exciting and really interesting. It is hard to describe everything in words, but it was definitely cool!

But onto the next challenge. After spending about one hour figuring out all the dependencies for some yacc-converting tools I am going to hack some interesting functionality together. Stay tuned for more information about this incomprehensible remark.

SUD 2007 roundup

2006-12-02T17:34:00.001+01:00

Warning: rather long story with a lot of my own opinions up ahead!

I attended my first Stratego User Days this week without really knowing what to expect. I had seen the titles of the talks, but some of them still made me wonder about what was going to be presented. So I took the train to Delft with sleepy eyes and a blank mind.

If you think that the SUD is like a conference then you are wrong, it is more of an informal gathering of people that use Stratego. They explain to each other what they do, how they handle problems and what they would like to see in the next release of Stratego. At first this gave me the idea that the room would be filled with _all_ of the users of Stratego, which was probably true for some of the earliest SUD's, but the first presentation of the day already proved that this idea was wrong. Martin Bravenboer started the SUD with a presentation about the current status of Stratego. He did not only explain how hard they worked on the 0.17 release, but also showed a list of papers and projects, including one complete slide about PHP-SAT, that use Stratego. Some of the people on this list use Stratego without any help from 'the core people', Martin and Eelco, so this probably shows that Stratego is catching on. Martin also mentioned that they are several (Phd) positions to fill, so if anybody is interested they should contact him.

Eelco Visser gave a presentation about the new compilation scheme of Stratego.The presentation was a bit too technical for me, but it showed some nice goals and resulted in a (short) discussion. The discussion ended at the moment that Eelco gave the right example by getting himself some coffee.

Martin continued after the break with a presentation about the new library structure of Stratego. He explained why almost all of the functionality is moved to the library in order to target the portability problem. The funny thing is that some of the presentations that where about to come would complain about this problem, which shows that the needs from the community are actually being fulfilled. I liked the fact that Martin gave lot's of examples that used php-front to illustrate the new features, always nice to see your own stuff used.

We had lunch a little late because we already hopelessly behind schedule, but it was still very nice. I have to say that I like the cafeteria in Delft, the money/food ratio is pretty good. The presentation of PHP-SAT started after the lunch and went very well. The people looked interested even after the moment that the laptop shut himself down because the battery was empty. Karl Trygve Kalleberg mentioned that IBM also had a project about static analysis of source code called Wala, but he did not remember whether it supported PHP. So I tried to find the PHP-part, but I could not find it so it is probably not supported.

Benoit Sigoure talked about his project in which he extended PRISM to deal with real life problems. I always enjoy it when somebody talks about projects that are really useful to them. He also mentioned some problems that he encountered and gave a 'wish list' of items he wanted to see in Stratego. I have experienced most of the problems he has and I totally agree with the fact that he wants some more static checking. One of the other wishes was a debugger and I would like to put this on top of the list. Being able to step through my Stratego program is something that would help me a lot, and others as well.

During the coffee break that followed the presentation of Benoit one of the girls in the room next-door asked me what kind of meeting we had. I explained the concepts of the SUD to here and she replayed with the phrase: ..I already thought that it was something with programming, you are all wearing those nerdy-code-t-shirts.., thank you very much indeed.

After I had probably been insulted by the girl, Mikal Ziane and Nicolas Pierron talked about Lutin. They use java-front and dryad to do some kind of code refactoring, but it wasn't completely clear to me. I think I might have understand things better if we weren't interrupted by the fire-alarm. It gave us a change to see some of the campus and the other people in the building, but it didn't help us to keep up with the schedule.

The presentation of Wouter Caarls about embedding Stratego in C showed another thing that can be done with Stratego. The techniques he used where not very complicated, most of them where also covered in program transformation course in Utrecht, but the combination was interesting.

Valentin David his presentation ended the day by giving an overview of the current C++-front-ends. This presentation was not very interesting to me because I (currently) do not use C++, but I can at least find it again when I need to. But during the talk he mentioned semantic designs, which offers support for analysis. They also have a front-end for PHP, so I probably should take the time to take a look at this.

The second day of the SUD started with a presentation about a system that comparable with Stratego, but written in Java. The system is called TOM and it has some very nice properties. They borrowed some features of Stratego and I hope we also will borrow some of their features. The small features, like matching on a sort without specifying the number of children or the not-match, are most likely not difficult to implement but useful additions to Stratego. They also showed an eclipse-plugin for their project and a graphical debugger, great things to have and very useful. Another project that is added to the list of things to checkout.

Another connection between Stratego and Java was presented by Karl Trygve Kalleberg. He showed the Spoofax project, which also holds a plugin for Eclipse. I haven't really thought about looking at this for the syntax highlighter for Context, but it might be a good idea to check how he did this.

Bernd Fischer gave a presentation about what he wanted to get from the Stratego community. Some of the ideas could also be useful for other Stratego developers, but most of his wishes could probably be solved by implementing a separate library for ACI1-terms. Some of the problems that he mentioned are actually handled by MathPert, so he might want to take a look at it.

The talk of Alexandre Borghi about vectorization was a bit to technical for me. I think I understand why you want it, but could not figure out completely how everything worked. I do not have a problem with this, I do not intend to use it in the near future, but other people will certainly find it interesting.

A presentation that was really interesting for myself was the presentation of Bogdan Dumitriu. He did his master thesis on improving support for data-flow transformations for Object-Oriented programs. Many ideas from his thesis and his talk are very useful for me and the PHP-Sat project, so I am definitely going to read the complete thesis. His support for break- and continue-constructs can easily be added to PHP-Sat and his ideas about customized transformations are definitely cool. As soon as a get a copy of the thesis, and some spare time, I will write a blog about these cool subjects.

My own version of the SUD ended with the presentation of Karl Trygve Kalleberg and Valentin David in which they present some ideas for extending Stratego. Some of the extensions, like an attribute grammar system, are already implemented in Transformers and look interesting. Other proposal are still in the 'this-would-be-a-nice-idea'-stage, so we will have to wait and see what the future brings us.

To conclude this roundup I wanted to say that the whole experience was very cool. It was nice to see what other people are doing with Stratego and was a good opportunity to do some feature-requests. I am already looking forward to the SUD of next year.

The SUD also gave raise to a great quote coming from Pierre-Ettienne Moreau which I probably will going to use more often. The quote displays a great sense of a pragmatic attitude which really appeals to me. During the presentation about TOM Pierre-Ettienne explained some side-effect that could occur during the application of a strategy. After someone asked him whether it was pure he replied:

..it is not pure, but it is practical.

Interesting things

2006-11-27T20:44:00.000+01:00

I noticed that it was already a week ago since I wrote my last blog, time flies when one is having fun. So this week should go really fast because all sorts of interesting things are going to happen!

The first interesting event is going to be the Stratego User Days where I will be presenting PHP-Sat. This presentation will be a bit more technical then my STC-presentation, but it will also contain the more theoretical stuff (I think).

The other even that is interesting, certainly for me, is that I am going to Dublin next Monday. I will be staying there for three days and I am going to do at least two interesting things there. I am part of the GSoc-group that is going to visit the Google Office. Someone else who was going to come was Paul Biggar, one of the people behind the Phc. It is to bad that I cannot meet him to talk about some of the problems/choices/gizmos involved in parsing and transforming PHP-code. But I will be meeting the other two authors of Phc. I am really looking forward to this meeting, it's going to be very interesting.

I promise that I will write about all of these events, so don't worry about missing all this interesting stuff. I am even considering to subscribe to something like Flickr so that I can share some pictures with you, although I think that the SUD will be covered by Eelco Visser.

For those people that want to read about something that actually happened already I have a little Doh-anecdote. I spend a day working on PHP-Sat together with Martin to fix the last DoubleQuoted string-ambiguities. The problem was that there where some literals that kept breaking apart within strings that where used for regular expressions. The reason for this was a missing follow restriction, so we fixed it and where very happy with ourselves. So I took another look at the problem yesterday and noticed that there where still more situations that showed this behavior. After about an hour I realized that we already fixed this problem for HereDoc by writing out the allowed order of literals and escapes. But I can not remember why we didn't do this for DoubleQuoted strings, isn't that interesting?

Who's idea is it anyway?

2006-11-19T17:52:00.000+01:00

I started with the research for my thesis proposal this week. For those who
wonder about the subject: please read on. For everybody else: skip to the next paragraph. My master thesis will explore an idea of Johan Jeuring
and Harrie Passier. The eventual goal is to provide feedback in educational tools (well actually educational tools that allow you to rewrite a certain input step by step to an answer), as if the feedback comes from a teacher. One of the hurdles that has to be taken is the guessing of which step the student wanted to take when a faulty answer is inserted in the program.
The idea for guessing this step is that you take the last correct tree and then generates all the trees that can be obtained by rewrite-rules that are allowed. You then calculate the difference between these trees and the faulty answer to find out which tree is nearest to the faulty answer. The rewrite-rule used to get this nearest tree is probably the rule that the student wanted to apply.
This simple and short explanation does not expose all the problems very well, but I will probably come back to that in a later blog. For more information about the idea you can take a look at this paper.

Last Monday I was in Leusden to meet the people from 'TeamInternet' again. Apart from going through some new code of the scoutshop, I also showed PHP-Sat to the people there. Bjarni van Berkum came up with a new idea for a bugpattern and this resulted in another idea. He told me that he was interested in the results of PHP-Sat on the code base because it would probably find the first pattern a few times. I told him that it shouldn't be hard to implement, but it turns out that this is not completely true.
I was right about the fact that it is easy to implement, for normal and static function calls that is. The retrieving of these functions are pretty straightforward because they are directly available in the environment. The problems lays in the fact that most of the codebase of TI is ObjectOriented, which means that there are lots of objects passed to lots of functions. But we currently do not descent into functions, nor do we know about objects. This poses somewhat of a problem if you want to find out which objects are used within functions. So unfortunately, there is a lot of work to be done in order to support this.

But there where more ideas that came from people at TI. Frits Zwegers talked about an idea for a tool that can give an overview of which files are needed for a given file. This can be done by collecting all directly included files and all the files that declare a class or a function that is used within the file. The implementation of this tool is also delayed because of the problem mentioned above, but I am pretty sure that it will be available some day :)

The people mentioned above already came up with great ideas, so if you also have a great idea: share it!

The first presentation

2006-11-09T21:02:00.000+01:00

The last three days where filled with only 1 thought:
Prepare Presentation

Every student that follows the master program at the Center For Software Technology has to give a talk as part of the Software Technology Colloquium. Students usually pick a topic that is researched by other people and present projects, ideas or tools that are the result of this research.

Since the ideas and concepts of PHP-Sat could be interesting for others as well, and since I already know some things about it, I started working on the slides and preparing the presentation. On Tuesday I practiced the talk and got some pointers on how to improve the structure of the talk. I gave the presentation today and it was actually fun to do. I was a bit nervous before I started, but after a few slides the story just came out very smoothly. So the first presentation of PHP-Sat was a success, on to the next one?

(For those who are interested, the announcement and the slides can be found here)

Something to celebrate

2006-11-04T17:32:00.000+01:00

This is the 50th post in this blog, a number to celebrate because it is a nice round number. It is also the first blog-entry that contains some real-world results, another thing to celebrate. It also comes at the time that I am reading the book The best software writing, thank you Michiel, which might help me to improve my blog-entries. Something that is definitely worth celebrating.

So let's look at some results. I found out that there 91 detections of pattern O000 in the PhpDocumentor-project. Since this suggests that you should always pre-calculate the size of an array I decided to do a little test. I first used the original sources of PhpDocumentor to extract the documentation of 'phorum', 'phpBB2' and 'phpMyAdmin'. After this I modified all the for-loops of PhpDocumentor that where flagged by PHP-Sat and extracted the documentation again.
The results where rather disappointing, maybe a single second somewhere, but nothing really substantial. When I showed this my girlfriend I realized that none of the projects have phpdoc-comments. So I found out that this optimization does not matter for projects that you would not process. Anyone else want to state the obvious?
So I repeated the experiment with the sources of PhpDocumenter itself, which are well-documented. The results for these sources are less disappointing. It turns out that pre-computing the size of the array saves 6 seconds in the frames/default configuration, and up to 9 seconds in the DOM/default configuration. These number are not very large, but it seems that this simple optimization really saves some time. If you want to know more about optimizations that are more useful, please click here

Optimization is nice, but has been discussed a lot and not very original anymore. So let's look at some results that indicate logical errors. A pattern that is not PHP-specific is C006, which is an ignored return statement. I have implemented this pattern because OWASP has an article about it. When I inspected the results I learned that Pear actually has functions that will always return 'true'. This situation is probably worth a pattern, but it also generates extra detections because the result of these functions are ignored.
But there also was an ignore that was not legit and this resulted in the first bug-report coming from PHP-Sat. Let's hope that it will get accepted and is fixed in the near future.

When I looked at the results from the C006 pattern I also read the comments in some of the files in Pear. The following piece of comment caught my eye:

.. constructor
@param ....
@param ....
@return mixed True on success else PEAR error class.

How can a constructor return either True or an other object? A constructor is supposed to return the newly created object, so a return statement in a constructor is useless. (PHP4 allows you to return something else from a constructor by assigning a value to the '$this'-variable, but this is not compatible with PHP5 or good practice.) I have also found a thread that shows that these patterns should be checked.
So I added the patterns C007 and C008 to PHP-Sat. I could not find any assignments to '$this' in the stable packages of Pear, but I found 13(!) occurrences of a return value within a constructor. Good luck for me, bad luck for the package maintainers?

A Doh-situation

2006-10-30T10:44:00.000+01:00

I had a real 'Doh'-situation yesterday, it happened when I was trying out php-sat on several PHP-projects. I began with trying php-sat on the sources of Phorum, phpBB, phpMyAdmin and Joomla.

The results for these projects are very nice, considering the current status of the tool. I was surprised to see that the pattern C003, which is very simple and even documented in the PHP-documentation, was actually flagged in both phpMyAdmin and Joomla. The functions to blame can be found in Table.class.php (generateAlter and generateFieldSpec) from the phpMyAdmin-source, and database.php (database) from the Joomla-source.

A pattern that was found quiet often in phpMyAdmin is pattern O001.
I have done some simple tests and it turns out that passing multiple parameters is roughly twice as fast as using concatenation. This blog-entry confirms this by explaining what happens behind the scenes in both cases.
So the pattern describes a possible optimization that is not very useful if this patterns occurs only once. But if it happens in 32 cases in a single source file that is called common.lib.php, which is probably used commonly in the project, then it might be useful to take a look at it.

But back to the 'Doh'-situation. After trying php-sat in the projects I wanted to run it on a large php-codebase. A great resource of PHP-code can be found in the PEAR repository. The PHP-code for PEAR itself is about 30000 LOC so I gave this to php-sat first. I was not surprised that it took a while because the code is pretty large. But I got a little suspicious after about 10 minutes of just seeing files being parsed. So I put some more log-messages in the php-front-library and tried again. It turned out that php-sat was including 3 files in a cycle, but the includes happened because of a 'require_once'. I was pretty sure that I had fixed this problem by checking whether a file was previously included, and this was indeed the case. The only problem was that I put the files that where included in the environment after going into a file. The solution is pretty obvious, but such situations just call for a slap on your own forehead.

Propagation

2006-10-23T21:43:00.000+02:00

So this week was still filled with constant propagation techniques, but also with software metrics. I have given a presentation about functional software metrics which was based on this PhD thesis. It is very hard to find papers about software metrics for functional languages, but it is even harder to find them for scripting languages! Please let me know if you know a website that covers metrics specifically for scripting languages, I don't expect there to be any papers about this subject.

I am looking for software metrics for scripting languages because I think that metrics can help in finding the weak spots in a program, but there has to be evidence to support this. Validation of software metrics is rather time-consuming, so hopefully done by somebody else :) It shouldn't be hard to make a tool based on php-front to generate a rapport with software metrics about your program, any volunteers?

But back to the constant propagation. I have added support for the propagation within loop-constructs, if-statements and switch-statements. This was not very hard because I could use the techniques described in this paper. The construct that was not discusses in this paper, or on any slide of the pt course (which is not given anymore, unfortunately), is the if-elseif-else construct. It is not very hard to come up with the (hopefully correct) semantics for this, but I could be wrong of course. I will explain my interpretation in the next section, but it might be hard to follow. Feel free to ask for a better explanation!

The if-elseif-else construct is evaluated as a list of list of statements. The first statement is used as an unit-element in a foldr over this list. This foldr applies a given strategy to every element, which is to be expected. But it also performs an split-and-intersect of the dynamic-rule-set between every two elements. The result of this is that the rule-set will only contain the dynamic rules that are stable in all branches of the if-elseif-else statement. The implementation of the switch-construct was pretty easy after I made the infra-structure for this "split-and-intersect"-foldr.

So the constant propagation is coming along very fine and is also added to the php-sat-tool. The new flag --complex-inclusion triggers the tool to perform constant-propagation and include the files that can be included in that way. The constant propagation is not completely finished, to consider this an 'alpha-feature in this 'beta'-tool.

Not the only one

2006-10-15T20:53:00.000+02:00

It is always nice to know that you belong to a group. I discovered this week that I am part of a large group of people that still works on their SoC project. It turns out that many people still try to work on their project, but at a slower pace. I am one of those people :) I am also one of the people that can walk around in a Summer of Code 2006 t-shirt (front,back), it arrived this week. But enough about bragging, let's talk about PHP-Sat again..

You will probably know already that Google has released Code Search, a search engine specifically for code. It turns out that it can be used to find vulnerabilities in PHP sources. The regexp for XSS due to echoing raw input, which is heavenly quoted on the Internet, gives around 7000 results. There are off course false positives in these results, but many of the results would be 'useful'. Could there be a better way to show that PHP-Sat is needed?

So I have been working on PHP-Sat and, more specifically, on the completion of the constant-propagation. I have rearranged the tests for the simple-evaluation. There used to be one big testsuite with over 450 tests on almost 3000 LOC. There are now separate testsuites for expressions, operators, primitives and so on.

Functionality is added in the sense that constants can now be defined and actually used. I have also begun with the implementation of references. The manual says that references are just pointers to the same memory location. I have mimicked this behavior by adding an extra step between a variable and its value. Every variable is rewritten to a 'variable-identifier', this 'variable-identifier' is rewritten to the actual value. Introducing a reference is now a simply introducing a rewrite from a variable to a 'variable-identifier'.

Oh, and I have also updated the implementation of pattern C002 to handle static function calls. Mmmm ... I should really put more time into those patterns.

New and Improved inclusion

2006-10-08T19:33:00.000+02:00

This week was not only filled with going to the university and playing around with PHP-SAT, it was also filled with (a lot of) preparation for the Flitsjacht, a game for scouts in our region. Organizing a game that is played by over 150 people in 11 teams in an area of about 10 square kilometers takes a lot of time, but the photo's are priceless.

Organizing this game does not mean that there is no progress on PHP-SAT, revision 256 holds a few new things. It includes some new tests, a few extra lines of source code and a lot of new functionality! The basis for the '--complex-inclusion'-flag is finished with the evaluation of the internal functions 'include','include_once', 'require' and 'require_once'.

The implementation of this evaluation was not that easy because of a small detail in the strategy 'find-in-path'. This strategy takes a list of paths and tries to find a file in those paths with a given file name. It does this by checking the existence of each 'path + file name'. This would always return the full 'path + file name', the next paragraph explains why this is useful, and worked like a charm. Until I tried it with a file name that was available at the current-directory! I did not get back the absolute path, but the original given file name. It took me a while to figure out that the strategy first checks for a file with only the given file name without taking the paths into account. I solved this by just looping over the list with directories and now everything is fine.

But why do we need the absolute path to include files? This makes it a lot easier to implement the logic of the 'include_once' and 'require_once' functions. Before we include a file we check if the file was already included by using the absolute path. The absolute path is necessary to prevent false positives in this case. False negatives are prevented by normalizing every path after a file is found. This normalization removes all '.' and '..' steps in a path and returns the direct and absolute path.

Next step: evaluate some more internal functions, especially the 'define' function that defines constants.

I love my test suite

2006-10-01T18:13:00.000+02:00

When I started to implement the evaluation of control-statements for the constant propagation I realized that I made a wrong decision. This occurred to me when I implemented the control-flow with a single if statement. One of the side-effects of such a statement is that it should undefine variables that are changed within the body when the condition can not be evaluated.
For example:

<?php
 $foo = 'bar';
 if($bar == 1){
   $foo = 'foo';
 }
//Value of $foo is unknown
?>

Because we do not know the value of $bar we do not know the value of $foo after the condition. So the dynamic rule that maps $foo to the string-value "bar" should be undefined. Stratego has special syntax for these kind of situations and this makes the implementation very easy.

When I wanted to do this for arrays I realized that arrays where implemented as a key-value mapping in a hashtable. This is correct, useful and it works, but undefining mappings takes a lot of work because the special notation would not work with this implementation. So I had to change this implementation and use dynamic rules.

My test suite really helped me in the refactoring of this implementation. It showed which part where updated correctly and I could use the tests to analyze why the rest still failed. It also made me aware of the fact the when a dynamic rule is undefined the key still exists. The application to this undefined key will always fail, as expected, but the key still remains in the set of all keys of a dynamic rule. The test suite also identified some hidden assumptions in the old implementation, which where immediately removed.

All this information would not have been available to me without the test suite. To quote a large company: "I'm loving it!"

And the answer is...

2006-09-26T22:03:00.000+02:00

Did you have enjoy thinking about the problem? I definitely had fun during this weekend, pictures will be put on the website soon.

But back to the question off last friday, what will be the result? It would not have surprised me if PHP would raise a NOTICE, but this is not the case. It might have surprised me if PHP used the last statement in the definition as the result, but this is also not the case. The variable $result is just null, not initialized, nothing happens! This is probably not the intention of a programmer, either the function is misspelled or the function is not correctly implemented. So this pattern is added to the correctness-category and has id C005.

I have also worked on the constant-propagation again. There is now support for superglobals and the list-statement. The support for superglobals also implies that every variable is also accessible through the $GLOBALS array.

Getting through the weekend

2006-09-22T14:32:00.000+02:00

My upcoming weekend will be filled with a lot of fun and excitement, I have another World Jamboree troop-weekend. Check out this site to see the other people of my troop.

For the people that can not spend a weekend without wondering about PHP I have a little exercise. What is the output of the following piece of code:

<?php 
  function foo($param1, $param2){
    $param1 + $param2;
  }
  
  $result = foo(1,2);

  echo $result;

?>

Will it be an error, the result of the function or nothing at all? Don't spoil the fun by running it in PHP without thinking about it! The answer was a little surprising for me.

I proudly present: the logo

2006-09-19T18:12:00.000+02:00

The PHP-Sat logo is made by Robert van Geenhuizen.
I am very grateful that he took the time to develop this logo. I think it is 'compleet hip', which means so much as 'very trendy'.

Robert made this logo with a concept in mind. The following quote describes this concept:


The creation of the PHP-Sat logo is based 
upon the following:

Develop a conceptually strong logo that 
uses modern illustration techniques to 
make a simple, yet strong ideograph.
This results in a "Bug" stopped by a 
imaginary (debug)-filter, the conceptual 
base principal behind PHP-Sat. 

The logo consists of many complex items 
with gradient mesh and three tints, but 
together they still form the basis for 
this strong and modern ideograph.

The statement is very hard to translate, so this is the statement in Dutch. If anyone can provide me with a better translation, please let me know.


Bij de creatie van het PHP-SAT logo is 
uitgegaan van het volgende:

Een conceptueel sterk logo neerzetten 
dat door middel van moderne 
illustratietechnieken een modern maar 
toch simpel en sterk beeldmerk is. 
Dit resulteert in een Bug die door een 
denkbeeldig (debug)-filter vliegt, het 
conceptuele basisprincipe achter PHP-SAT.

Het logo bestaat uit veel complexe items 
met verloopnetten en 3 kleurtinten, maar 
toch vormen zij samen de basis voor dit 
sterke en aanwezige, moderne beeldmerk.

Here it comes:

What is going on?

2006-09-17T20:02:00.000+02:00

If you have been wondering about what is going on, here is the answer. I have attended a conference of the NLUUG last Thursday. I actually worked there to check badges, but I could also attend the talks that where given. The main reason for being at the conference was the change to talk to people that would probably be interested in PHP-sat. I gave a demo to some of the partners of madison-gurkha, which went well I think. They where introduced to me by Armijn Hemel, who has a brother (Tim) that works there. I already presented the tool to Tim last Monday and he seemed to like it too. He is even learning Stratego to be able to adapt the tool.

Armijn also helped me out with some typo's in the documentation and with testing the tool. He found some things that where not support by the SDF. Some of them where rather easy to fix, others require an update of Stratego or a post-processor for the parsing.

If you have checked the issue tracker recently you might have noticed things are a bit more organized now. I have added some milestones to be able to plan more. So you can check out the roadmap to see what is going on.

Another thing that is going on is the creation of a paper. I have to write a paper for the STC and Martin suggested that it would be nice to write for a real conference as well. I will try to get it published so that the project will get an even more solid foundation. But I will certainly talk about the project at the STC and maybe also at the Stratego User Days.

To conclude this entry with a cliffhanger, the logo for the project should be ready very soon!

Anything new?

2006-09-13T08:49:00.000+02:00

Sorry for the late update, college is really getting started so I have to get used to going to lectures and meetings again. But my php-*-projects are still going strong. The evaluation strategy can handle construction of, assigning to and reading entries from arrays now. An array in the interpreter is modeled as a map which maps keys to values. Some useful strategies have been implemented to easily add and retrieve values from the arrays. The documentation about arrays tells us that PHP also sees an array as a map, so the implementation of the semantics was not that hard. The only thing that it does not support (yet) is references. These will be added later.

The second thing that has been added is the fix for the long lasting psat-2 bug-entry. This states that HereDoc should be parsed as a sequence of literals and escapes, just like double-quoted strings. This turns out to be very tricky. Double-quoted strings have a very straight-forward start and end-point, HereDoc does not have this. The end of a HereDoc is marked with a newline-label-newline sequence. So the newline was added as an escape in a literal, we have to treat this newline in a special way if it is followed by a label. The problem that arises here is that we cannot express this within SDF. This should be written down as a follow-restriction on the newline, but then we would have to know the length of the label. This length is not fixed, so we can not do this. By not setting the follow restriction a literal became ambiguous when there was a variable in front of it. The solution here was to write out the definition of 'a list of literals or escapes'. This definition was extended by 'where there are no two literals in a row'. This solved all the problems for that moment and everybody was happy!
This happiness lasted until I tried to parse a file with a statement after the HereDoc, this failed. So a statement after a HereDoc caused the parser to keep parsing until the end of the file, something that we definitely do not want. So the problem here was that the end of a HereDoc was not strict enough. I tried several things, but nothing seemed to work. The optional semicolon was causing big problems. It turns out that this optional semicolon was a misinterpretation of the documentation. The documentation mentions this semicolon and I thought that it was part of the end of the HereDoc. But this semicolon is only allowed because the HereDoc is probably part of a bigger expression that needs to be closed by the semicolon. So I simplified the HereDoc-end and this allowed a nice follow-restriction. All the problems are over and everybody is happy again :)
So there is now a more expressive support for HereDoc, with a restriction. This was already true with the first implementation, but never really mentioned. The problem is that one can not express the fact that the labels of the HereDoc should match within SDF. So HereDoc is parsed from the first open label until the last closing label, even if there are statements in between. This restriction is unfortunate, but reality for all parsers that are based on SDF. It is simply not possible to solve this within the syntax definition. It can be solved by adding a post-processing step, so an issue for this is already created.

The finish this entry with some good news, there are windows-builds for both php-front and php-sat! It took us some time and some hackery implementation of stratego-routines to get everything right, but we succeeded. The hackery stuff will be moved to the stratego libraries as soon as possible. I have tested the build on my own machine and it seems to work fine. Please try it out if you have a windows machine that you can (ab)use. Windows-builds for stratego programs are relatively new, so there could be some hidden problems.

Finding differences

2006-09-06T18:11:00.000+02:00

Here is another example that shows that testing is useful. I had implemented the type-juggling from Integer- to String-value and written some tests for this. All the tests succeeded on my machine so I could commit. I was surprised when I got a mail about a failing build. If you look at the page then you will notice that the check passed for i686-linux, but failed for i686-darwin. The tests that fail have in common that they handle a non-empty string that does not start with a number. Thus my code applied string-to-int to an empty string. This strategy is implemented in C and calls strtol. It turns out that the result of this function is not the same for both platforms if the input is an empty-string. I am not a C-expert, but i686-darwin seems to give an error and i686-linux does not do this. The problem is solved and tests are added to the Stratego-libraries for this. But it might be useful to know for others.

These implementation details might be interesting for some, others prefer an update. So what has been added to PHP-SAT? It is now possible to include files in a simple way. This means that all files are included without looking at the context. They can only be included if the file names are coded in Strings, so no concatenation. They should also be on the include-path. But this is the same for PHP.

It is also possible to print the included files. All files are printed to a file with the same file name and a post-fix '.psat'. The bug patterns within PHP-SAT are also applied to the included files, so these are checked automatically.

I am currently improving the simple evaluation to be able to handle more complex file inclusion. It should also improve file-inclusion by having the normal semantics for include_- and require_once.

The last cool thing is that almost all calls to the stratego-xtc-library are gone. This means that we could make windows-builds soon!

Thanks and progress

2006-09-02T20:33:00.000+02:00

I think that there are many people with great ideas for projects. Most people do not get around to actually starting up these projects. It takes a lot of time which is usually not available. Without the Summer of Code I would not have had the time to start the project, let alone work on it for so many hours. Thank you Google!

The project would not be in his current state without my mentor. He helped me in setting up the development environment and automating the build- and test-process. Our meetings motivated me and helped me in keeping focused. I would recommend all (future) participants of the Summer of Code to meet with his/her mentor face-to-face, or at least in some interactive way. It helped me a lot, thank you Martin!

The following section is taken from my evaluation for the Summer of Code. I think it nicely summarizes the current progress of the project. The project has produced the following two libraries, together with tools to interface with them.

PHP-Front is a library with support for parsing and pretty-printing php, reflection of parsed sources, some generic traversals and a simple evaluation. This part is available as a separate package which provides a solid basis for transforming or inspecting PHP source code. I think that there will be more projects that are going to use this package for this purpose. One of the projects that I am already aware of is StringBorg.

PHP-SAT is the library that actually performs an analysis on the given source code. It tries to detect 7 bug patterns, more will be implemented later. It also check pre-conditions for functions and language construct to detect possible vulnerabilities. This last analysis will be improved over time.

Introducing eval-php

2006-08-30T17:49:00.000+02:00

After spending a weekend in the woods, hearing a lot of information about the World Jamboree, I dived into the operators of PHP. Some of them could already be evaluated, but I wanted to add support for other operators as well. I have made a tool to check the evaluation and named it 'eval-php'. This tool is capable of evaluation a subset of PHP. It cannot handle control-flow (yet?), but it can support several operators on the integer, string, null, Boolean and float type. The following list of operators are supported:

Small note about the arithmetic operator 'mod'. It has no support for floats until issue STR-630 is fixed.

This also means that the bitwise operators, error control operators and execution operators are not supported at this moment. But as said before, it supports a subset. Supporting the Error Control operator when there are no errors generated is a bit strange anyway.

It is fun to be able to evaluate thing, but it is even more fun to see things that are evaluated. So the tool produces evaluated output. This means that everything that is not within PHP-tags is outputted. There is also support for the 'echo' statement, so this produces output too. I have put a small test-file online here. The output of eval-php is available here, it can be compared with the real output of PHP itself here, take a look at the source of the page.
I think it is all pretty fancy :)

Working on evaluation

2006-08-25T15:54:00.000+02:00

I have been working on evaluation the past few days. Not the evaluation of the SoC, this is something I am going to do that next Monday, but that of PHP. The reason for this evaluation can be found in the first blog of Monday.

There is currently support for arithmetic operators on the following types: integer, float, Boolean, null and string. Types can also be juggled to an other type. It took some time to get this juggling right. Especially the juggling from String to numbers. The string is now sort of parsed within Stratego to get the part that can be recognized as a integer / float. But it works :)

Speeding things up

2006-08-23T18:41:00.000+02:00

There has been some major performance boost implemented today. The build and tests of the package took about 7 hours in the build farm, which is a lot. Even for Stratego standards and even if it is build on 3 different platforms. The problem was the processing of the test-input. A lot of small inputs are processed by writing it to a file, parsing the file and reading the result. This involves a lot of IO actions. So the inputs are not written to files anymore. This helps a little, but the major boost came with caching the parse tables. The parse-table is now opened once for every process instead of every test / input.

Splitting up

The project holds two libraries in it's source. The first library is php-front and holds a parser, pretty-printer, a reflection part and a set of common strategies. The other library holds the strategies that are used within PSAT. The PSAT-part depends on php-front. The base library can be useful for more libraries and will be branched from psat soon. It will be a separate package called, how surprising, php-front. It will be available here. You can also find a link there to the page that will be the home for php-sat. They will both be filled soon.
Note that the name has slightly changed. This is to prevent confusion with possible tools that will statically analyze Perl, Phyton, Pascal, PL or Prolog. The other reason is that psat.org was already taken. All the names will hopefully be updated as soon as the packages are separated from each other.

Project deadline

2006-08-21T16:45:00.000+02:00

The project deadline is today at 17.00 hours, at least here in Holland. This means that the project is due in a few minutes. My mentor needs to fill in the evaluation based on the code that I have now.

This deadline does not mean that the project will stop. I am satisfied with my results up until now, but I will continue to improve the code and the tool. A more elaborate report about the SoC and the progress of the project will probably follow in a few days.

Including files and hidden tasks

2006-08-21T10:23:00.000+02:00

File inclusion within PHP can really work on your nerves. I can remember an occasion when it took me about an hour to find out why a file was not included. This was because PHP first looks in the working-directory and then in the current directory. If there is a file with the same name in both directories the first one is included. If I had taken a look at the documentation then this would not have come as a surprise to me.

Way this paragraph about including files? Because this feature is added to php-front. There is now a strategy available that uses the 'require' and 'include' statements within a PHP-file to find and parse other PHP-files. These PHP-files are added to the environment and can be accessed anywhere in the traversal.

The implementation of this inclusion strategy included the modeling of the different paths that PHP used. As mentioned above, PHP uses two different directories to search for files. The working directory, where the process was initiated, and the current directory, where the current file resides. These directories are the same if there is only one file to be processed.

I did not want to mess with the current-directory of the tool when including files, so the paths are kept internally. This requires some string manipulation to make up the right include-path, but it works. By keeping track of the include-path and working-directory within the application there is even support for the functions ini-set and chdir!

All this could not have been done without moving things around and adding some small but useful strategies. This included: a separate section is added to the library that holds common strategies, the parsing is moved to the library and the environment can now store complete AST's. All of these things are small and easily done. But unfortunately, many small things take up a lot of time.

The mechanism of including files can be improved by adding partial evaluation of PHP-code to the library. This will add annotations with known values to terms. By using this, and some constant-propagation, the following will succeed:

<?php
    $path = './some/path/';

    require_once $path.'filename.php';
?>

This is commonly used within projects so this should be supported. So on to the simple evaluation and constant-propagation!

One week later

2006-08-17T19:08:00.000+02:00

I flew back from Spain yesterday evening, no problems with my luggage, and spend this day getting everything organized again. I had planned on going to Lowlands this weekend, but I have to skip it this year. But I will join the party again next year I hope.

But what have we done the past week. I have added a few patterns to the code:

The last one needs some work though, the rest of the function-names should be added to the list.

I have also spend some time on improving the pretty-printer. I have added unit-tests for the different parts (expressions, statements, documents) and made sure that things are consistent. An example of this is that every construct that has a list of expressions is printed in the same way. The expressions in the list are separated with a comma and a space. A small example:

 //used to be:
  array($foo,$bar,$fred);

  //is now
  array($foo, $bar, $fred);

I have also made the strategy that extracts the safety-type build a default value of 'Safe()'. This makes the application more conservative because if it has no knowledge about a variable it will consider it to be safe. This should prevent a lot of false positives.

The last item of interest is a small document with some considerations about constant propagation and including files. The response to the user should show the code that the user has entered. So constant propagation should not be done on the current ATerm, but the information should be added to it. The only thing I could come up with is to add the information in an annotation. But if you have a better idea don't hesitate to comment.

Relaxed working

2006-08-09T16:45:00.000+02:00

It is not easy to get some work done while there is a private pool nearby, but I managed to get some things done. I have added the syntactic rules that make sure that an end-tag ends a line-comment. This involved another rule that recognizes nothing as a constructor. The follow-restrictions are really important in this case, but I think I managed to get them right.

I have also added the right syntax for backticks. This syntax is quit similar to the syntax for double-quoted strings. So the productions that make up the double-quoted strings could be reused to make the syntax for backticks.

A small note

2006-08-04T13:46:00.000+02:00

I have added two more patterns to the correctness category. They have the codes C002 and C003. The last one is also mentioned in the PHP manual, but it can't hurt to point this out to the programmer. The other thing that I have added is the test-suite-file for the tests of phase 4. This suite contains only two tests for now, but more will be added during my vacation.
"Until next time, take care of yourself and each other."

working on other things

2006-08-03T22:13:00.000+02:00

I have done interesting things today, but they did not all involve psat. What I did for psat was the adding of a strategy "analyse-safetylevel" to replace the "annotate-sources" strategy. This strategy is set up in a different way to make it easier to add support for other constructs.

What I have also done for psat is changing the way safety types are combined. My first thought was to combine safety types if they have the same level. Variables can then have the safety types "escaped-html" and "escaped-slashes" at the same time. This is something one would expect.
However, combining safety types of other levels would results in variables that can have both the safety types "formatted-string" and "encoded-string", or even "object-type" and "integer-type"! This is definitely not desirable. So the only types that can be combined from now on are the types that are on the "escaped-something"-level. Writing this makes me realize that I will have to add some more terminology.

You might want to know what other activities I did today. If you are not interested you might want to skip this paragraph. I have had my first experience with compiling and installing PHP on my linux machine, a nice little laptop. Quit nice, but the real cool activity was a pair-programming session with my mentor. The commit-message of the result can be found here. And the module with my name in it is located over here. Always nice to have your name in a software package that you are using a lot.

I have also finished setting up my laptop as a development environment. This had to be done because I will be flying to Spain on Saturday. One and a half week of nice weather, a private pool and a lot of relaxing. I will be working on some things during my vacation, so don't panic :)

straight to phase 4

2006-08-02T22:49:00.000+02:00

The tool has upgraded from phase 2 to phase 4. This is the current phase that needs to be implemented. I will give a short sketch of what the tool supports at this moment, besides a hand-full of common patterns.

The tool is configured with a text-file of which some sections where explained yesterday. A default configuration file can be found here. This is definitely not complete, but it already produces useful results.
Two features are added to the configuration file. The first feature makes it possible to define a precondition for the language-constructs 'echo', 'die', 'exit' and 'print'. The syntax for this is:

 construct: construct-name (  precondition  )

The second feature is the possibility to define functions with a default level. This can be done in the '[function result]' section. The functions that are specified there are assumed to always return values with the specified safety-type. This is not limited to build-in functions, user-defined functions can also be assigned a default safety-type result.

But which results are produced? The following example shows two things that are supported right now:

< ?php

      echo "hello ", $_GET['name'];   //is flagged

      print $_POST['param'];  //is flagged
?>

Keep in mind that the results depend on the configuration. These results will appear when the default configuration is used. A more precise configuration will give more precise results.

From phase one into phase two

2006-08-01T22:56:00.000+02:00

Major leap today. The implementation of phase one is ready. This phase consisted of parsing a configure-file and using this configuration to identify tainted sources. A typical configuration file for tainted sources will look like this:

 [tainted sources]
     array: _GET
     array: _POST
     function: file_get_contents

But then there will be a lot more entries off course.
The configuration file is used because people should be able to easily tweak the tool. This is why I have also included the option to specify a certain level for each source. A little example:

 [tainted sources]
     array: _GET   level: escaped-slashes,escaped-shell

This means that the variables coming from the $_GET-array return values in which both slashes and shell-characters are escaped. These safety-levels are used in the static analysis.

That was phase one, on to phase two. This is also a configuration file-issue, namely the identification of sensitive sinks. They can be specified in almost the same way as tainted-sources.

[sensitive sinks]
     function: foo ( safe )
     function: bar ( int-type, esc-h )

This configuration file means that the function "foo" expects one argument and this argument should have the safety-type "safe". Function "bar" has two parameters which should be of "integer-type" and "escaped-html" level. For each parameter the safety-type should be specified. Parameters in which the safety-type does not matter can be assigned the type 'unsafe'.
One can also specify that a certain parameter needs to have one of more types, or it must have multiple types.

[sensitive sinks]
     function: foo ( esc-h || esc-sh , esc-h && esc-sh)

This means that the first parameter needs to have either the type escaped-html, or the type escaped-shell. The second parameter needs to have both types, and thus levels, of safety.
There are two things to consider when writing such a configuration file. The first one is that it does not allow functions without parameters. This is not that strange because what is the use of a sink in which nothing can be thrown? The other thing is that the and- and or-operator should be used with care. Since the level that are specified represents the minimal level of safety, the safety-types that are used in operators should be of the same level. The following represents something that must be both safe and unsafe. Which can only be true when the variable given has type 'safe'.

[sensitive sinks]
     function: foo ( safe && unsafe )

Tomorrow I will be adding some more configuration details for the sensitive sinks. Some language constructs must be configurable and it does not take very long to add this. I will also be working on checking the safety-types of parameters given to sensitive sinks. So the first useful results should appear soon.

Reflection support

2006-07-31T22:26:00.000+02:00

Sometimes you have to reflect on something, and it is now even possible in php-front. The inspection of functions during a traversal was already possible, but the first implementation also retrieved all the functions within classes. Since these functions are not in the global scope this could result in some serious errors. So this is fixed and support is added for classes and interfaces.

To be able to do reflection in a analysis you have to create an environment and initialize it so that it contains all the functions. This is off course captured in some strategies so it is very easy. The only thing that you have to do is make a choice between an environment for PHP4 or PHP5. The grammar is split up in this way and I found it more cleaner to also separate the
environment. This is also use full when the internal functions are added to the environments. PHP5 has a few more of those.

The reflection library is constructed in the same way as the dryad-library. It is actually set-up in a OO-way. So there is a notion of an PHPEnvironment, which is abstract, and a PHPFunction, which is also abstract. Each version has his own kind of environment and function which makes it easier to reason about.

The only problem is the implementation of all this. It requires very careful thinking and precise notation. It is very easy to confuse some strategies and this can result in some long debug sessions. But luckily each part of the reflection is carefully tested, but that is normal right ;)

Results from the meeting

2006-07-28T23:29:00.000+02:00

So this afternoon I talked to my mentor. Several things where discussed and all of them where positive. The structure of the code for the project was good and organized. Only some miner points about the formatting of the code. Really not a bad result. He also has a cool idea about the organization of the patterns. We might be able to organize it in such a way that patterns can be plugged in at will, which will really boost the extensibility of the tool. But we will have a look at that later.

Then there was an issue of the type-states. After the response of Christian yesterday I have come up with a set of safety levels. Each variable in the program will be assigned such a safety level. When a computation is made the result will get a level of safety which is normally the minimum of the levels of the variables involved. The sensitive sinks will get a precondition for each parameter. This precondition describes the minimal level of safety needed for that parameter. When a variable does not meet the precondition the function will be flagged by the tool. Simple isn't it :)
Since the preconditions will not be equal for all applications, and some functions can be trusted sometimes, the configuration regarding sensitive sinks and tainted-data sources needs to be configurable. I will be writing a small syntax for three ini-files that allow everyone to tweak the application.

The last thing that we did was making a start with the reflection-library. When traversing the tree of a program it is use full to have access to the functions and classes that are defined. Since some of the functions are defined by the user there should be a way to access the implementation of the functions. This can be done by traversing the tree every time a function is needed. You can imagine that this is expensive. So the trick is to traverse the tree once and build up hash-tables for things that one wants to access frequently.
So it is now possible to get the AST of a function by it's name. So when a function call is made the implementation of the called function can be retrieved on the spot. I will have to add support for classes and some more strategies to get interesting properties of the AST's, but I now know how to do it. A lot of new and fun stuff to do!

Adding patterns

2006-07-27T20:47:00.000+02:00

Today I have added the documentation of eleven bug patterns: C001, O000, O001, O002, O003, S001, S002, S003, S004, S005 and S006. You can find the description of each of the patterns here. Remember that each category has it's own prefix, so you will have to look within the directories.

I have also added the tests and implementation for patterns C001, O000 and O001. The patterns that are not implemented yet have [Not implemented] in their description. They will be added (hopefully soon).

Their was also some disappointment today. I received a reply from Christian who I had mailed yesterday. They can not share the research that they have done regarding the list with preconditions and type states. The algorithm has been put in the products of Armorize Technologies. Sharing the crucial part of your products is not a good idea for a commercial company it seems :)

But he gave me some pointers on how to start, so that is what I will be doing tomorrow morning. I will be having a meeting with my mentor about the set-up off the tool, but I think it is okay.

Testing 3 4

2006-07-26T19:42:00.000+02:00

I have added support for SUnit tests to the project today. This also includes some tests for the two patterns that where already in the tool. I have also added tests and the implementation for a style-pattern. This one has the code, you can probably guess it, S000.

It took me some time to get all the tests working and the compilation of the tools is not that fast. So I have the feeling that I am not making that much progress the last few days. But the adding of patterns an such should go a lot faster now because there is a method to do it. So I can focus on the implementation of the patterns instead of how to add them.

I have also send an email to the authors of the paper I mentioned yesterday. I hope to hear from them soon because I am reluctant to start the implementation of the phases. They should have a lot of use full information which I can use. I will wait until Friday and otherwise I will just have to start with the phases. So I will be adding patterns to the tool as fast as possible until Friday :)

A long one

2006-07-25T20:28:00.000+02:00

After a whole day of doing research I just had to do some coding. So that is what I did today. I have added the basic stuff to add 'bug patterns' to psat. This should not have taken long because the detection of these patterns can be very simple. So I could have done this by simply dumping the rule in a file be done with it. The rule is certainly put into a file, but I have also added a directory structure within the library to make sure that the patterns stay organised.

As my mentor mentioned, the patterns should be organised. It is natural to put each pattern into a certain category. The following categories seem to be use full to start with:

Style
Correctness
Performance
Malicious code vulnerability
Information leak

The first three are straightforward. The fourth category is mostly dedicated to the initial goal of PSAT. The last category will hold bug patterns that can expose data which is not intended for normal users and should not be shown in a production environment. Each category will get his own directory and each pattern will get his own file. Each pattern will also get an unique code which holds the category and the follow number.

The first bug pattern to be in PSAT is using the If-construct to check the existence of a variable. This pattern falls into the category of Correctness and therefore has the code C000. I know it is a bit optimistic, reserving space for 999 bug patterns in one category, but you can never be sure :)

I also wanted to write something about the categories of the functions. While I was reviewing them I thought about how different functions need different escapes. A query can hold HMTL-characters but needs to have escapes for all the quotes to prevent SQL-injection. Data that is send to the user should escape slashes, but also HTML-tags. So I will have to go over the collected functions and give each sensitive sink a certain level of safety needed. This is the same approach as the one taken in [1] and it seems to work there. They have implemented this in a tool called WebSSARI, but the site of this tool seems to be deleted. So I will try to get in contact with the authors of the tool, but it probably means a few hours of research.

1: Yao-Wen Huang, Fang Yu, Christian Hang, Chung-Hung Tsai, D. T. Lee, and Sy-Yen Kuo. Verifying web applications using bounded model checking. In DSN, 2004.

Doing research

2006-07-24T17:38:00.000+02:00

I have to do some research before I can start with the different phases of PSAT. Some of that research is relaxing and fun to do, an other part is quit annoying. Let's start with the first part. Since I want to add the possibility of providing feedback about code smells I have to find code smells to give feedback about. Besides the topic on GoT I start reading up on my subscription to PHPArchitect. I still had to read four issues, now two. You might wonder why this is fun to do. Well, I have a balcony with just enough space for a hammock and I have printed the issues. You can figure out the rest yourself.

But there was also a more annoying part. I have to divide the internal functions of PHP into three major categories:

Functions that can return tainted data
Functions that can untaint data
Functions that are sensitive sinks

See the Terminology section of the Phase description for some explanation about the terms.
When I was going over the list I also made a list of functions of which the information should not go to the user. Such as functions that retrieve all kind of information about the system.

It is interesting to check out which functions PHP has, but it becomes less interesting when there are over 3500(!) internal functions. So I spend my day was with reading function-descriptions, but I have at least seen all functions. I will explain some more things about the categories tomorrow. I will also add some stuff to the tool that will make it actually use full :)

And what have we done today?

2006-07-21T20:44:00.000+02:00

This morning I worked on the actual psat-tool. It parses a file (using parse-php), applies a strategy to the ATerm and pretty-prints it (using pp-php). The strategy it now applies is:

strategies
  dangerous-variables = topdown(try(matchthing))

rules
  matchthing: Simple(_) -> Simple("foo")

So what does this do? It matches on a Simple-node and gives it the name 'foo'. This means that every variable ('$name') is renamed to '$foo'. Not really use full, actually quit bad, but it shows the power of what can be done. Two actual lines of code and all variables are renamed.

This rule will be deleted in the next commit because it is not use full. But what is use full then? I have asked the people at GoT and gotten some reactions. Still hoping for more feedback off course.

The other thing I worked on today was the specification of the phases. I had a plan two posts back but I rewrote it a bit after some feedback of my mentor. The result can be read here.

The last thing I did today, besides writing this entry, was making the pretty-printer simpler. I had a strategy that rewrote a list of statements, but the framework could do this for me. The cleaned up about 30 lines of code, which is always nice :)

Adjusting the plan

2006-07-20T20:02:00.000+02:00

Today was filled with some bug fixing and new ideas. I have fixed a few small things in the pretty-printer that caused the failure of test-cases test-cases. I admit, I was a bit optimistic yesterday. The results of the round-trip tests is looking very cool now, if you want to see a lot of sunglasses I suggest you take a look.

The new idea came from martin in his reply to the phases-description (which I will rewrite/improve tomorrow). The idea was to add other indicators for bugs to psat. Just simple things that can help developers to improve their code. One example of this is the usage of a variable that is not declared. This can great problems if register globals is on. Another example comes from the PEAR-coding standard for including files. Adding these use full remarks would turn PSAT into a PHP-equivalent of FindBugs, which has a long list with descriptions. Some of them also use full for PHP.

But I could not find lists of specific code smells for PHP. There are some general code smells that can be used, but I think there are more things specifically for PHP. So if you have any ideas about what a PHP-programmer should not do, or tricks that can improve the performance of PHP-scripts, please let me know.

Pretty problems

2006-07-19T22:43:00.000+02:00

Today was a wonderful and, for Dutch standards very, hot day. The fan in my room was pointing at my computer instead of me to keep the temperature of the processor at a decent level. So what has been done in this heat for psat? The pretty printer is somewhat finished! If you take a look at the parse-results you will see a lot of cool smilies. There are just some minor problems to be solved. A trailing slash at the end of inlineHtml and some diff that do not go as planned. Some of the constructors could also be printed prettier, but this is something that can always be done.

I decided to split the pretty-printer into three different tools. Just as the parser is, so one where you can specify the release and two tools for the specific releases. Consistency is always nice. I have also added constructors and pretty-print rules for the alternative syntax. The reason for this is that the same constructor could have children of different formats. This introduces if-then-clauses in the rewrite rules which are not really intuitive. With specific constructors I could also print the alternative syntax in the same way.

The next phase(s)

2006-07-18T15:32:00.000+02:00

The round trip has been added to the test-script. The new smileys should be popping up soon in the parse-results page.

Since the pretty printing is coming along fine, I considered the phases for PSAT itself. I have also posted this to the psat-dev list. But this could also be discussed here off course. Any comments or suggestions are most welcome.

Phase 1:
Identify and annotate the variables that come from the user with 'un-safe'
This includes the research of which variables can be altered by the
user. Some info

Phase 2:
Identify and annotate the functions that can cause vulnerabilities
to occur if a 'un-safe' variable is used.

Phase 3:
Generate a rapport in some form to show the user the possible vulnerability
At the end of this phase the following should give use full info:

 echo $_GET['name'];

The design of the rapport is also considered in this phase.

Phase 4:
Identify and annotate the functions that make variables safe for use
within the 'un-safe' functions. The annotation should also be added to the variables used and propagated.

Phase 5:
Add support for assignment variables and the (simple) propagation thereof

Phase 6:
Add support for reference variables and the (simple) propagation thereof

Phase 7:
Add support for the propagation within and coming from(user-defined) functions

Phase 8:
Add support for the propagation within and coming from objects

Notice that the phases are build upon each other. The base-foundation
is made in the first four phases, the simplest case. The other phases
each add a layer of complexity. Each phase should result in a working
tool that supports the mentioned constructions.

Back from the woods

2006-07-17T17:33:00.000+02:00

Great wheat er, great terrain and nobody has become ill from my cooking, a successful trip. Now that I am back the fun is starting again. The pretty-printer can parse all literals such as variables, strings and operators. There is some support for expressions, but more will be added tomorrow.

The test-script will also be expanded with a pretty-print,parse,pretty-print and diff round trip. The difference between the original pretty-printed and the parsed-pretty-printed version should be totally empty off course. This will show the 'correctness' of the pretty-printer. If everything goes according to plan then this will be also be finished tomorrow. The script that is...

Tools!

2006-07-12T17:13:00.000+02:00

What is the thing that every programmer wants? Tools off course! The current revision 74 has a few tools that let you parse php-files to the ATerm-format. 'parse-php' is a common tool with a option to choose the release you want. For everyone who wants to have a separate tool for each version we have 'parse-php4' and 'parse-php5'.

The other tool that is available is 'pp-php'. This tool will pretty-print a php-file in ATerm format to an actual PHP-file. This will also be tested with the distribution files, but it is not yet finished. It supports variables and operators. The rest will be supported as soon as I come back. Yes I'm going away for a couple of days to cook for a group of girl-scouts. So no ATerms, SDF or command-line tools for a few days.