The reaction to flashCHESSIII has been overwhelmingly positive, especially on forums, even though the blog entry received just a reply.

Advanced chess players were expecting a tougher engine though (some players have estimated an Elo rating of of 1500-1800 for the engine).

The first time I compiled and run the engine, after weeks of just writing code, it could evaluate about 1000 moves per second. After heavy optimizations using the Flex Builder profiler, which helped me identifying the trouble areas, the speed increased gradually to 10,000 moves per second. A ten-fold increase may sound impressive, but lets put it in context.

The number of nodes (possible moves) evaluated per second results in how "deep" the search can go - how many plies the computer may think ahead. Consider the game opening. White has 20 possible moves; for each of there, black has another 20 possible moves. So, at depth (ply) 1 we have 20 moves; at depth 2 we have 400 (20*20) possible moves; and so on, depending on how many pieces we have on the board and how much they can move at a given moment. The number of moves increase exponentially. Even with alpha-beta pruning (eliminating searching of nodes that cannot be beneficial) at depth 4 we have around 10,000 nodes (moves), while at depth 5 we’d have 150,000 nodes, 500,000 nodes at depth 6 and so on.

So, my Actionscript 3 engine can do 10,000 nodes/second, evaluating 4 plies ahead (it could go to about depth 5-6 by setting the Script Limits to timeout after 60 seconds instead of 15, but who waits that long?). A similar engine in terms of features, but written in C can do around 300,000 nodes per second. A really powerful engine like Crafty can do over 1,200,000 nodes per second. Deep Blue could do 200,000,000 nodes per second, evaluating up to 40 plies ahead.

Why so slow? First and foremost, Actionscript 3, while quite fast, is still run in a virtual machine that runs in a browser… it’s no match an application written in C. From my tests I’ve found Actionscript by to be 5-10 times slower than Java and 100-500 times slower than C.

Also, with Actionscript you can’t do any fancy multithreading or take advantage of multiple cores a system may have or a 64bit architecture (using bitboards would speed up calculations tremendously, but they require 64bit integers, preferable with hardware support; the Number type in Flash is only 57 bits long).

Then we have the memory issues. Because chess evaluates so many moves and board combinations, sometimes the same board position may occur in different parts of the search tree. Chess engines store this kind of info in what’s called Transposition Tables - which is a fancy name for a cache. Strong PC-based chess games sometimes allocate more than 200 Mb of RAM for this cache. Obviously, for a flash application I can’t do this unless I want to hear a lot of complains, so I’m clearing the cache after each search. It’s still used, just not as effective.

Finally, it’s the evaluation function. After each move, the board needs to be evaluated, that is to see the effect of that move. At its core, it counts the value of the pieces for each player. Then you can reward certain positions (castlings, two rooks working together, etc) and much more. You can spend years just tweaking the parameters and scores.

Still, it’s great fun. I could never understand those who start creating chess engines until I did that on my own. It’s a great challenge to think of new ways to improve both speed and effectiveness.

I hope to release beta 2 tomorrow…

After too many sleepless nights, I’m now confident enough to show it to the world: flashCHESS3, a complete chess engine written in AS3.

Our old actionscript chess engine was written when AS1 was still in beta, and had many shortcomings, but was very popular nevertheless. The new game is written completely from scratch and uses most features you’d expect to see in a chess game. The search depth is limited by default to 4 plies, although by extending the script timeout limit to 60 seconds it can go to ply 6 on my laptop. It has support for all chess rules (the old game couldn’t handle en-passant) and unlimited undo.

I’m still planning a few features, like saving and loading the game, some tutoring aids and maybe a board editor or at least a way to import/export the board as a FEN string.

I’d be delighted to hear what you think of it - just keep in mind that its main purpose is to entertain, not to be a very strong engine (after all AS3 is no match for C or even Java).

The sites

I first saw it mentioned on Slashdot earlier this year but I only experienced it a month ago. Legitimate websites, with "infected" javascript. For example, it’s the standard swfobject.js but with a long line of obfuscated code at the beginning, looking like this:

document.write('<script language="javascript">$="%64b%3d%22%3c7`7%3c [lots of code deleted] %3b";eval(unescape($));document.write($);</script>');

What it does is to create a hidden div, which contains an iframe, which links to a malicious website.

Then I wondered how could all these sites become poisoned (according to various sites, the number of compromised websites range from 10,000 to 100,000 - see this article on BBC). One popular theory is SQL Injection. In some cases however, I knew the sites and their owners; we’re talking about flash sites, with no database and even no server-side scripting - plain html and/or flash. In these cases, I think malware such as ldPinch might have been used. Trojanized cracked software could lead to sites ftp passwords being stolen and allowing attackers to "poison" the websites. Oh, Linux servers are vulnerable too.

The Poison - a.k.a. attack vector

The site to which the hidden iframe points may use various exploits - I’ve seen Quicktime exploits and Adobe Reader exploits. This is interesting (and worrying) because it doesn’t matter what browser you use - if your version of Reader is vulnerable, you could be using Opera or Firefox. It would work even with javascript turned off. I’ve read about trojans for Mac OSX being used too but I didn’t test myself.

Even more worrying (and the reason for this article) is the increasing number of flash player vulnerabilities reported, culminating with the one reported in April 2008, which lead to the new flash player version 9.0.124.0 - get the whitepaper from IBM or the explanation of the attack. Just one month later, flash is hit again with a remote code execution vulnerability, which at the time of this writing is being investigated by Adobe. What’s really scary is that this vulnerability is already being exploited ‘in the wild’ so compromised web sites are already serving it via MPack. UPDATE: Flash player 9.0.124.0 is not affected, the vulnerability targets earlier versions.

If you’re still unconvinced of the seriousness of the situation, some light read about MPack may help (adapted from Wikipedia):

MPack is a PHP-based malware kit produced by Russian hackers. First released in December 2006, it’s being updated monthly and is thought to have been used to infect more than 100,000 computers with backdoors.

MPack is sold as commercial software for about $1000 and is provided with technical support and regular updates and add-ons, with variable cost depending on severity of the exploit and the ability of antivirus software to detect it.

The server-side part customizes attacks for browsers including IE, Firefox and Opera. MPack generally works by being loaded in an IFrame attached to the bottom of a hacked website. When a user visits the page, MPack sends a script that loads in the IFrame and determines if any vulnerabilities in the browser or operating system can be exploited.

The kit includes a management console, which allows the attacker to view statistics about the computers that have been infected.

If you had any doubts: malware is no longer a hobby - it’s an industry; it’s organized crime.

Protection

15 years ago it was enough to have an up-to-date antivirus. 5 years ago, an antivirus and a good firewall/NAT would have been adequate. Nowadays we need multiple levels of protection just to decrease the likehood of being infected.

Hardware NAT/Routers/Firewalls are a good solution to prevent against remote attacks via worms by blocking unused ports and separating the internal network (NAT = network address translation; several computers in a network will share one external IP; from outside the NAT, no one can target a computer inside the network). They don’t protect at all against local exploits (viruses, trojans, etc.)

Stateful firewalls and antispyware can alert the user for suspicious activity - programs trying to send to the internet when they are not supposed to, etc., but some programs are expected to use the internet (if you grant your ftp program access to the internet, if it’s trojanized it could send saved passwords as well, unless you monitor every port and every remote address).

Antiviruses work against viruses and other malware but guess what - the malware makers test their ‘products’ with the antiviruses too and are doing their best to make their stuff as difficult as possible to detect.

Running as a limited user (not as root/Administrator) is a sensible thing to do and may limit the damage if the malware get through the other layers. It’s still not bullet proof.

Educating the user to avoid downloading pirated software or to install codecs requested by movies from bittorrent or to open executable files is necessary too, although by itself it doesn’t do much.

Virtualization

Lately, virtualization is being promoted as a method to limit malware’s damage. The concept is to put a whole operating system inside a virtual machine. For the host OS, it’s just an application, the virtual harddrive is just a file. The guest OS is mostly unaware that it’s not running on a real computer and has access only to those devices and resources permitted by the host.

There are a number of virtualization solutions, from the ubiquitous VMWare to the little VirtualPC to the enterprise-grade, OS-integrated Hyper-V.

I have a number of virtual machines for testing purposes - ranging from a Windows XP used to test new software, to a CentOS running a LAMP (Linux, Apache, MySQL, PHP) environment.

Virtualization is currently hailed as a ’safe’ way to work. It makes sense in theory - software running inside a VM can’t "escape" in the real world. Or can it? The flash player is a VM, and code running on it could compromise the host OS. Malware can determine if it’s running on a virtualized system (most of them run additional tools to aid integration, such as VMWare Tools or Virtual Machine Additions and the virtual hardware configuration can provide hints). Specially-crafted code could compromise the virtual machine itself and allow for arbitrary code execution - it already happened for all VM software.

The Future

It’s an escalating battle. For years, viruses were made by teenagers, mostly for fun. Now it’s all about money (via stolen e-bank password, spyware, pop-ups and who knows what else), so the malware creators are organized and unfortunately it’s looking like a losing battle, in that it requires increasing effort to protect oneself, and I haven’t even discussed about botnets.

If we look at email and spam, we can see where this is leading. Sure, we use spam filters, greylisting, SPF (sender policy framework), CAPCHAs and more, making our lives miserable in the process and spam still gets through in our inboxes (including GMail), in blogs and everywhere.

I may be in a pessimistic mood, but it looks to me that the bad guys are winning. Prove me wrong. Please.

Some of my old friends keep asking me for tips and tutorials for flash and actionscript, so I decided to spend a few hours writing a small tutorial for a small slideshow class. The tutorial turned out to be rather long, because I wanted to go in detail and explain the "why", not just the "how".

The code is AS3 and the tutorial assumes some general knowledge of flash and actionscript 1 and 2.

Read more »

Pages: 1 · 2 · 3 · 4 · 5 · 6 · 7

I just read on Google’s official Webmaster blog that they’ve started experimenting with more advanced crawling to help them index pages inaccessible via links. Their crawler is actually filling and submitting forms from the site and check the results.

From the blog:

Specifically, when we encounter a <FORM> element on a high-quality site, we might choose to do a small number of queries using the form. For text boxes, our computers automatically choose words from the site that has the form; for select menus, check boxes, and radio buttons on the form, we choose from among the values of the HTML. Having chosen the values for each input, we generate and then try to crawl URLs that correspond to a possible query a user may have made. […] our crawl agent always adheres to robots.txt, nofollow, and noindex directives. That means that if a search form is forbidden in robots.txt, we won’t crawl any of the URLs that a form would generate. Similarly, we only retrieve GET forms and avoid forms that require any kind of user information.

The idea definitely sounds interesting, but I can’t help myself wondering how this might have unintended consequences. Why?

It all boils down to so many programmers failing to understand the differences between GET and POST and when to use one instead of the other. To many, the distinction is simply "GET is easy to test, ‘cause you can test the URL in browser; POST hides the parameters". This is not the whole picture though.

GET is intended to be used to, well, get data. A search form is a prime example: you enter a word and the server gives you back a list or results.

POST is for actions. Login is a good example, but basically any action that actually alters anything should be handled via a POST, although very often it is not.

I’ve seen plenty of cases where actions are sent via GET, query strings like ?action=delete&itemid=1131. Can you see the potential issues? Now, granted, googlebot will only crawl though public areas (they won’t touch password fields and such) so the damage should, in theory, be limited. In practice, the bot will try all possible combinations of a form’s widgets, like an automated tester but without the benefit of running in a supervised environment.

My advice? Have a look at your code and remember "if something can go wrong, it will". If you see something not quite OK, better fix it now.

Further Reading:

• HTML 2.0 Specification - Form submission