Grad School

The Halting Problem is no problem after all…

Science Journalists … hmmm

“…Microsoft researcher Byron Cook and his colleagues did the unthinkable — they hacked a fix. When Cook tried to describe the workaround, however, he found it impossible to explain with existing mathematical symbols. His only option, he decided, was to invent new ones…” – from Wired

Rejecta Mathematica!

Rejecta Mathematica is an open access, online journal that publishes only papers that have been rejected from peer-reviewed journals (or conferences with comparable review standards) in the mathematical sciences.

I like their philosophy…

Hello Iranians, The Arabs are Jealous

Yes, they are jealous. No, not because the Iranian leaders get 63% as opposed to the 99.1% their Arab neighbors never fail to score. It’s a bit more complicated than that…

We’ve all seen the – let’s call it – the unsuccessful counter-revolution in Iran. We’ve seen the green protests in every major city in the world. We’ve seen the riots being applauded by almost every Western leader. We’ve seen the Western media romanticize about the love of freedom. We’ve seen Twitter, Facebook, and Youtube empowering the freedom-hungry Iranians. And that’s all good, but there’s something hypocritical in all of this.

The Western powers lead by the US believe in freedom where it’s in their best interest. What would happen if the 80 million Egyptians started similar riots against their police state? The simple answer: US aid to the government to contain the situation. The detailed answer: As long as the Mubarak administration is following the US orders, the Mubarak administration is safe. Mubarak is in their best interest, he keeps the middle east “balanced”. Forget about his policies, forget about the dictatorship, he is a friend of the US. If the US really cared about freedom, why was Obama’s speech to the Muslim nations broadcast from Cairo? Why did he fail to criticize the lack of democracy in Egypt, Jordan, Saudi Arabia, and the list continues?

Why did the Americans and their friends boycott the democratically elected Hamas government in 2006? Why are they supporting the corrupt Palestinian Authority? Well, you get the pattern by now: because it’s in their best interest. Do you think that if a third Palestinian revolt (Intifada) against the occupation is started in the age of Twitter and Youtube, Twitter and Youtube will open their doors widely to the voices under occupation? I don’t think so, at least not in the same hospitality the Iranians enjoyed. This is why the Arabs are jealous.

Why aren’t we stylish?

I’ve been reading William Zinsser’s On Writing Well. Zinsser stresses on developing your own writing style. He says it doesn’t come easy, but with practice – as many other things – it comes. Over the past 8 months, I read a good number of research papers, but I only saw the same dull template and the same writing style in each and every paper as if they were generated by a program (maybe a good idea, input results, output paper, publish). Is it the mathematical nature of the papers I’ve been reading? But even the ones I read for the empirical research course (i.e. papers with more English letters than Greek letters), the same seems to apply to them. Am I just not reading too carefully to observe style? Is it because I’m an amateur researcher?

Still, why can’t we free ourselves from this writing “style” that we have somehow as a research community agreed on? Is it because we don’t want papers to be ambiguous? Is it because we want them to be easy (read: boring) to read? Research papers should be cooler and if we don’t want to change the status-quo, maybe we should allow the researcher a page or two after each paper to freely talk about their work. Just let them rant for a page or two, let them say what they want to say the way they would describe it to you in person.

PhD or no PhD?

When I finished my undergrad degree, I wanted to go to grad school and get a PhD. And here I am in grad school with 9 months left (hopefully) for my masters degree. There are many reasons why I had the PhD in mind. I like what I do – formal methods. I find it interesting, challenging, and important on a larger scale. I also didn’t want to go and get a job and code for 40+ hours a week, but that’s not to say I don’t enjoy coding.

But now I’m having second thoughts about the whole research thing. As I mentioned, I think it’s interesting, but after having spent 8 months in a research setting, reading papers, attending seminars, talking to other students, I ask myself the question: Do I want to dedicate 4/5 years of my life to tackling a very specific problem to which my answer may never be looked at? Of course, 4 years of intense research expand the mind and elevate many skills (and add two letters before your name). But I go back to the question of is it worth it. I’ve never worked at a company, so I can’t make any comparisons between a research/academic setting and a corporate setting. Starting my own company? I don’t know. I don’t have any ideas at the moment that I think are worth risking a year or two for. Maybe I should ask myself where do I want to be. But then this poses another question: What will take me to where I want to be?

Neitzche once said (or wrote):”Many are stubborn in pursuit of the path they have chosen, few in pursuit of the goal.” I guess I’m still trying to figure out both, the path and the goal.

The Road to Palestine: The Soldier, the Sun, and My Passport

For Palestinians, going into and out of Palestine is not the most pleasant experience. It involves preparing the endless number of IDs and passports depending on what kind of Palestinian you are (living in Jordan, living in Palestine, living in Palestine with a Jordanian passport, and other categories I do not understand and even people categorized under them do not know why they are categorized as that)

After you make sure you have everything and that all your documents are not expired, you have to go through a countless number of checkpoints with a high probability of being insulted and oppressed. In this post, I document my experience of getting from Amman, Jordan’s capital, to the city of Ramallah in Palestine. Palestinians cannot enter their country directly, they have to enter through Egypt (if they’re going to Gaza) or Jordan (if their destination is the West Bank).

In a normal world, you only need your passport to cross a border, with, perhaps, a travel permit stamp on one of the pages. Getting into Palestine needs a bit more than that…

The documents

Ladies and gentelmen, from left to right, top to bottom, we have:

1. The Palestinian ID: a document saying that you are Palestinian, something you have to have on all the time in case you get stopped on a checkpoint.
2. The Jordanian military service booklet: A useless document since there’s no obligatory military service in Jordan anymore. It takes forever through bureaucratic process to get one, and it essentially has no use.
3. The permit: every time you exit Palestine, you have to buy one of those and you use it on the way back in. When I was leaving the West Bank at the end of the summer, it took 3 or 4 days to get one as the Israeli government wasn’t printing them. They were sold in the black market.
4. The Jordanian passport: Why? Well because the West Bank was annexed to Jordan before falling under Israeli occupation in 1967.
5. The yellow card (as we call it): officially known as the “crossings card”. It’s a Jordanian document given to you if you’re a Palestinian, documents when you enter and exit Palestine. Palestinians living in the West Bank are given a green card (no, not the American one). The green card, let’s just say makes your life a lot more complicated in Jordan.

Next step: Off to the dead sea where the crossing is. We call it “the bridge”. You hear “the bridge” all the time, going to the bridge, coming from the bridge, stuck on the bridge, lost his bags on the bridge, denied from the bridge, etc. etc. etc. Even poems were written about The Bridge!

First you wait on the Jordanian side of the bridge. I got up at 2 a.m. and got there at 4 a.m., and it was packed. People race to the bridge, but no matter how early you arrive, someone always beats you to the bridge. “Do people sleep on the bridge from the day before like on boxing day?” I wondered.

This is how the lineup was at 5 a.m. in the lowest altitude on planet earth in summer heat:

The line up on the Jordanian side of the bridge at 5 a.m. (300 people in front of me?)

I then waited until they started work at 7, I think. After getting through all the formalities of checking your passports you wait for the bus. Jordanians send buses to the crossing, and Israelis let them in one by one to check them, and sometimes you wait a long time in the bus just to cross the tiny, almost non existing Jordan river.

The bus finally

…The bus goes on the bridge, the legendary bridge. Thanks to the Japanese government, we have a concrete bridge now. But it was always exciting going on the wooden one.

The bridge!

After the bridge … Palestine! … well occupied Palestine. The bus stopped on an Israeli checkpoint in the middle of the desert, we got off the bus, they checked our passports and checked the bus then they let us go…

checkpoint in the middle of nowhere

Then we got to the main border building or what we call “The Israeli Brdige”, as opposed to the “Jordanian Bridge” on the other side. Welcoming us was this poster:

$10,000,000 if you have information about these two guys lost in Lebanon in 1982. They probably have to update the pictures

It has the pictures of two army men lost in Lebanon in 1982. It says “10,000,000$ for any information…”

Inside, you line up, get checked, line up again, get your passport signed, etc. They had pictures of King Hussein of Jordan and Yitzhak Rabin shaking hands and smoking cigarettes. “Peace” they call it…

Late King Hussein of Jordan and the assassinated Israeli prime minister Yitzhak Rabin

Then we got on another bus that took us to the Istiraha in the city of Jericho where we can take cabs to other cities in the west bank. But first the Palestinian authority had to check us and check the bus as well. I don’t know what to think of this, ironic or sad?

Palestinian Authority

Nice building PA!

And this is where you take a cab to your city of interest (Ramallah in my case):

And at the end…after a bumpy cab ride, I got to Deir Ghassaneh, my village near Ramallah. I needed two things when I got there, to sleep and to shower. I was in the sun all day, carrying my luggage from bus to bus, going from one window to the next getting some document stamped by someone with a funny accent.

I will end with the words of Darwish who spent so many years in exile, in airports, and on bridges:

“My country is not a suitcase
and I am not a traveler”

Who’s Running this Country?

“How did so many millions of decent Canadians come to be ruled by such a weird government?” Robert Fisk – a man who needs no introduction – wrote in his latest article for the Independent. “Why is he saying that?” You may ask. What’s wrong with our government? The answer is simply: A disastrous foreign policy that ’s tarnishing Canada’s reputation around the world.

Let’s start with one of the most recent decisions: Banning George Galloway from entering the country to give talks that were scheduled in a number of cities across a number of provinces. Jason Kenney, Canada’s Minister of Citizenship, issued a statement through his spokesman describing Galloway as a “threat to national security”. I cannot comprehend how a 5 time elected British MP  would become a threat to Canada’s national security. Yes, he was in Gaza the other day delivering food and supplies to the dying and war scarred Palestinians. Yes, he met with Hamas leaders, a terrorist organization on Canada’s terrorism scale. But a number of British politicians and diplomats expressed interest in holding talks with Hizbollah lately, does that make them a threat to national security? I went to one of Galloway’s speeches in Toronto two years ago, it was peaceful – no guns. Our national security before and after Galloway’s visit remained the same, so why not let him speak this time? In the end, Kenney’s decisions simply gave Galloway’s speech more hype and publicity. On March 31 2009, he spoke to sold-out crowds via video link from the US, where he is not considered a threat to national security.

But this is not Jason Kenney’s only highly questionable action lately. He cut funding to the Canadian Arab Federation (CAF) who uses the money to run language training courses for new Arab immigrants. This came, according to an article in The Calgary Herald on March 20 2009, after a display of Hamas flags at one of the protests against the war on Gaza and after Khaled Mouammar’s, the president of CAF, verbal attacks on Kenney. Kenney should engage in dialog to understand immigrant minorities instead of using the power of funding to change them. Aren’t debate and dialog what this country stands for?

On March 26th in a UN resolution vote on deploring “the recent Israeli announcements of the construction of new housing units for Israeli settlers in the Occupied Palestinian Territory, as they undermine the peace process and the creation of a contiguous, sovereign and independent Palestinian State,” Canada was the only country to reject the resolution. It did not abstain, it blatantly rejected it. What does that imply? Is Canada supporting illegal settlements on occupied land? Our government has simply reached new heights.

In the first week of March during the Israeli Apartheid Week (IAW), a number of university campuses particularly in Ottawa banned a poster with an Israeli fighter plane shooting a missile towards a Palestinian child in Gaza. The poster was not even exaggerating, it simply portrayed the truth of January’s massacre when hundreds of children were, literally, torn apart and buried under the rubble by the Israeli war machine. But that wasn’t the only thing, IAW was attacked by politicians from every end of the spectrum. “Criticism of Israel is legitimate. Attempting to describe its very existence as a crime against humanity is not.” Michael Ignatieff wrote describing the message of IAW in an article published in the National Post on March 5 2009. The question to Ignatieff is: Who described Israel’s existence as a “crime against humanity”? Calling Israel an apartheid state refers solely to its policies towards the Palestinians in the West Bank, Gaza, and Israel. I am guessing that Ignatieff has never visited the occupied Palestinian territories. Maybe he should.

Finally, I want to mention the torture that a number of Canadian citizens endured torture in foreign land under the consent of the Canadian government. Of course the first one who comes to mind is Maher Arar. Arar was tortured in Syria before he was returned to Canada. Abousfian Abdelrazik is not allowed to come back to Canada, he is now in Sudan. Abdelrazik lives in the Canadian embassy waiting to return after having been imprisoned and interrogated several times by the Sudanese government under the consent of our government. Abdullah Almalki had a similar story to that of Arar’s; tortured by the Syrians and imprisoned for two years after they received a letter from the Canadian government accusing him of al-Qa’eda ties. He is back in Ottawa now after his vacation. At this point we do not have any information on whether there are more Arars and Almalkis having vacations sponsored by the Canadian government in some exotic spots.

Let’s stop this.

My Research Direction

For my master’s degree research project, I’m going to focus on combining static analysis and dynamic analysis. By static analysis, I mean an analysis over an abstraction of the program (e.g. model-checking). On the other hand, dynamic analysis refers to the concrete execution of the program (an actual test – unit test). The basic idea is to deduce test cases from the abstraction, and use the result of the test cases to refine the abstraction until a solution is found.

Here’s a survey of some of the work done on combining static and dynamic analysis:

1. Yogi project: An ongoing project at Microsoft Research that checks safety (reachability) properties of a program by using an abstraction from which they obtain test cases. If the test case reaches an error, then – well – the error is reachable. Otherwise, the result of the test case is used to refine the abstraction by splitting a state. The abstraction is an over-approximation of the program (i.e. it contains more behaviour than the actual program), therefore it can’t be used to verify that an error state is reachable since it may be a spurious path. We can only use the abstraction to check unreachability. This means that if there error state is reachable, the only way the algorithm can figure that out is by finding and a test case that can get us there. Their approach is sound but obviously incomplete. Check out their SYNERGY algorithm paper.

2. Counterexample Guided Abstraction Refinement via Program Execution: Building on top of the CEGAR framework, this work of Kroening et al. replaces the counter-examples that are used to refine the abstract model by concrete execution traces. The example they go over in the paper contains a lot of non-determinism (external input to the program). They exploit that fact to guide the program to reach the error state, it allows them to monitor the progress and provide input accordingly. But what if the program only contains non-determinism at the beginning (i.e. arguments to a function)? Will their approach handle it?

3. Testing, Abstraction, Theorem Proving: Better Together!: In this paper, Yorsh et al. execute the program on a number of tests. They then take the concrete states resulting from the tests and map them to abstract states via an abstraction function. They then check if that is enough to conclude the value of the checked property from the abstraction, if it is then they make a conclusion, otherwise they add more tests to cover uncovered states in the abstraction. From what I understand, the choice of the abstraction function and the initial test cases is dependent on the user. Their technique may result in false alarms.

There’s also more work in this area of research, for example, Check n’ Crash.

Most of the above work deals with an over-approximating abstraction. I am thinking of going in the direction of combining over- and under-approximation and then using test cases to refine the abstraction.

Also, most of the work in this area relies on a theorem prover or a linear program solver to generate test cases. I am thinking of using something along those lines, or asking the question: How would a professional tester do it? So, basically, try to come up with a set of heuristics for my test case generation.

I would like your feedback on this. Is there any important work that falls in the category of dynamic and static analysis that I didn’t mention? For coming up with a set of heuristics, are there any recommended books on testing?

we’re in deep in trouble!

When a new grad gets hired and the news hits the front page of CNN, I think it’s a bad sign:

cnn.com : March 5th 2009, 9:33 a.m. EST