2011 in review
The WordPress.com stats helper monkeys prepared a 2011 annual report for this blog.
Here’s an excerpt:
A San Francisco cable car holds 60 people. This blog was viewed about 3,300 times in 2011. If it were a cable car, it would take about 55 trips to carry that many people.
World Community Grid: The Human Proteome Folding project
The Boinc software application (http://boinc.berkeley.edu/), developed in the University of California, Berkley, allows every personal computer to use its unused computational power to solve tasks automatically downloaded from the Internet from projects benefitting humanity like the World Community Grid (supported by IBM http://www.worldcommunitygrid.org/). Global statistics about the WCGrid can be found at http://www.worldcommunitygrid.org/stat/viewGlobal.do.
WCGrid is a virtual supercomputer who’s power will help address whole range of humanitarian concerns from healthcare, AIDS, cancer, finding better strains of rice that are more nutritious. It is an amazing opportunity for people to get involved in humanitarian issues. WCGrid is doing a study of all of the proteins in rice to come up with stronger strains of rice to improve the World food supply.
IBM’s innovation technology allows people to donate the unused power of their individual computers to address problems in the world and this is a new level of contribution-donating something that costs nothing to the donors, that they do not use and can make change in the world.
A huge work is invested to secure the widely open volunteer system. There are people in IBM called “ethical hackers” who are paid to try to hack the open access grid.
WCGrid is harvesting spare processing time from computers around the world using that computing power to accelerate research. One half of a million years of computer time has been already donated to important research projects in the WCGrid.
Explaination about World Community Grid by IBM’s How it works at http://www.ibm.com/podcasts/howitworks/021307/index.shtml
Human Proteome Folding Explained
Crockford: JavaScript’s bad and good parts
Douglas Crockford, a programmer involved in the ongoing development of JavaScript, popularizing the JSON (JavaScript Object Notation) data format and currently a senior JavaScript architect at Yahoo!, have wrote a book and gave talks about the good and bad parts in JavaScript proving that most of the professional developers using JavaScript are not aware of the beauty of a programming language hosted on more virtual machines than anything else on the planet—on every fully-capable web browser. With a series of interesting examples Crockford outlines the most common problems in developing JavaScript applications, provides workarounds and outlines the good practices.
ECMAScript is widely used for scripts executed on the client (Internet applications separated between the server and the client) in the form of well known dialects like JavaScript, JScript and ActionScript. There is a project to the ECMAScript’s dialect JavaScript as a server-side engine (Node.js).
JavaScript is criticised by advanced developers in other programming languages for its weak type system and lack of raising proper exceptions, but it is irrefutable that there is no such programming language in the world like JavaScript, which to be used by such a wide range of users- starting with copy-and-pasters to professional software developers using JavaScript for scientific purposes.
ECMAScript supports object-oriented programming. Objects in ECMAScript are values with named properties. Object properties that are functions can be called as methods. ECMAScript functions are objects and can be stored as properties, passed as arguments, and returned as results. This powerful idiom from functional programming allows your functions and methods to import functionality from their caller in a simple and flexible way. ECMAScript objects inherit properties from prototype objects. Prototype-based programming facilitates easy delegation and flexible overriding of object behavior. [About ECMAScript. http://www.ecmascript.org/about.php]
Crockford’s experience reveals that JavaScript is a language that people use without bothering to learn it first.
JavaScript’s Bad Parts
- Global variables: Due to the lack of a linker in JavaScript, compiling took place in a global namespace where any variable can collide and interfere with each other. XSS attacks are fundamentally enabled by JavaScript’s use of global variables.
- Operator + adds and concatenates: This overloading in a type-unsafe programming environment causes problems.
- Semicolon insertions: JavaScript tries to put semicolons instead of the programmer in order to make the C syntax easier for beginners. When the compiler gets an error, it goes back, looks for a line feed and replaces it with a semicolon.
- Operator typeof: JavaScript typeof operator returns for the type of an array object and for the type of null object.
- With statement: slows the execution too much.
- Eval function: mostly misused function in JavaScript.
- Phony arrays: While in most languages arrays are linear sequences of memory divided into regularly spaced buckets where easily an address can be computed to the element in the array, in JavaScript arrays are essentially hash tables in which the keys are turned into strings. Due to this behavior arrays have a terrible performance in JavaScript, but makes the programming model easier as an array’s dimension is not set.
- == and != do type coercion.
- Too many bottom values like false, null, undefined, NaN.
Consequences of type coercion of the double-equal operator (very strange and ruled by a complicated rules- http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-262%20edition%205.1,%20June%202011.pdf Section 11.9.3 The Abstract Equality Comparison Algorithm):
'' == '0' //false 0 == '' //true 0 == '0' //true false == 'false' //false false == '0' //false false == undefined //false false == null //false null == undefined //true " \t\r\n " == 0 //true
JavaScript has a triple-equal operator which checks types in making a comparison. The triple-equal operator is highly recommended.
The for in operator is troublesome as it makes a deep dredge on the all members of the object.
Blockless statements, expression statements, floating point arithmetic, ++ and — operators, switch operator are a bad heritage. Switch statement is replaced by advanced JavaScript developers with an object encapsulating the possible cases of the switch block (http://www.sitepoint.com/google-closure-how-not-to-write-javascript/).
JavaScript’s Good Parts
- Lambda.
- Dynamic objects: At any time a property can be added to an object. Developer does not need to add the property to a class. Dynamic objects turned out to be amazingly powerful. A form of reflection occurs in JavaScript when you ask an object about the value of a property which it has not-JavaScript returns undefined.
- Loose Typing.
- Object Literals: a very nice notation for describing objects. JavaScript’s object literals were the inspiration for the JSON data interchange format.
Inheritance in JavaScript
Inheritance is object-oriented code reuse. There are two schools: classical and prototypal. Prototypal inheritance is class-free where objects inherit from objects. In JavaScript an inherited object contains a link (named __proto__) to the parent object. This inheritance is called Delegation or Differential Inheritance.
Below is a pattern of object creation with inheritance in JavaScript:
function myPowerConstructor(x) {
var that = otherMaker(x); /* create an object by Object literal,
or with new keyword,
or Object.create,
or call another power constructor */
var secret = f(x);
that.priv = function () {
... secret x that ...
};
return that;
}
Variable called “that” (without the quotes) is used to contain the new object. Please note that “this” (without the quotes) is a reserved name. The variable “secret” (without the quotes) is private. Method called “priv” (without the quotes) is a closure and, thus, has access to all private variables and can be invoked by the outside world. Closures are functions referencing the environment in which they were created (their context).
Right-curlies (“block {” all on the same line) is the only acceptable style in JavaScript. Due to the insertion of semicolon on every line returning an error a return clause must be followed on the same line with a right-curlie or a value.
JSLint
JSLint is a code quality analyzer for JavaScript code freely available at http://www.jslint.com/ . JSLint defines a professional subset of JavaScript. It imposes a programming discipline that makes developers much more confident in a dynamic, loosely-typed environment.
Chess BFS search with heuristic static evaluation functions. Parallel algorithm on OpenMP
Garry Kasparov (World Chess Champion 1985-2000) vs. Deep Blue (IBM’s chess engine) in 1997
IBM’s DeepBlue analyzes 200,000,000 possible moves per second (brute force approach) with an array of 256 CPUs.
I would like to present you my long-term project-A Chess game engine using Breadth-First Search with static heuristic evaluation functions. Chess is a two-player zero-sum game. The worst the possible moves of the opponent are, the better is your move. I have used an open-source chess player Beowulf v. 2.4a and have move it to use OpenMP to become parallel. The Beowulf is the chess engine of ChessBrain project, a project winning a world record for computation in 2004, networking together 2,070 computers located in 56 countries to play a single game of chess. OpenMP is a portable, scalable model that gives shared-memory parallel programmers a simple and flexible interface for developing parallel applications for platforms ranging from the desktop to the supercomputer.
Due to their special structure, tree search algorithms can be naturally parallelized (data parallization: the same function running on a parallel environment processing different input, compared to functional parallization where the processing units take semantically different input), which makes them a very attractive area research in parallel computing. The main elements of tree search algorithms include the following [Yan Xu, Scalable Algorithms For Parallel Tree Search, 2007].
- Processing method: A method for computing path cost and testing whether the current node contains a goal state.
- Successor function: A method for creating a new set of nodes from a given node by expanding the state defined by that node.
- Search strategy: A method for determining which node should be processed next.
- Pruning rule: A method for determining when it is possible to discard nodes whose successors cannot produce solutions better than those found already or who cannot produce a solution at all.
Theoretically, the fundamentals of chess program have three major segments: move generator, evaluation function and search algorithm. Decision tree that is the base of search algorithm grows exponentially with factors depending of position, hash tables, number of pieces on the board… If we suppose that on the first level of the decision tree one has node with normal 40 exists, on the second level it will be 402 = 1600 nodes, on the third 403 it will be 64000 etc. It is obvious that number of nodes and processing time depends exponentially of the level – depth of the search tree. In theory, that effect is called combinational explosion. On the other hand, the quality of computer play strongly depends on depth of the decision tree so the effect of the exponential explosion limits the computer chess strength. There are generally two approaches to overcome this problem: Shannon-type-A [By the name of its inventor in 1949 Claude Elwood Shannon (1916 – 2001) (See http://chessprogramming.wikispaces.com/Claude+Shannon)] (full-width approach) and Shannon-type-B (selective search). The first one tries to solve the problem by using the simple pruning mechanisms based on Alpha-Beta technique with idea to decrease maximally the time needed to compute one single node. This approach benefits maximally of the rapidly increasing speed of the modern CPU-s and also incorporates standard (cluster) parallelization. The second approach (Type-B) is concentrate on heuristic pruning based on relatively extensive portion of knowledge directly programmed into the evaluation or move generator function. This approach is very depended on the programmer skill and the quality of the implemented pruning, so the results could be very relative. On today’s level of knowledge in this area, the best combination is to use near full-width approach in main searcher, and selective searcher in q-search (quiesce) procedure. The algorithms could be combined: Alpha-Beta, Null Move and PVS (NegaScout). [Vladan V. Vuckovic, The Method of The Chess Search Algorithms Parallelization Using Two-Processor Distributed System, Ser. Math. Inform. Vol. 22, No. 2 (2007), pp. 175-188]
Why Quiescence Search? The problem with abruptly stopping a search at a fixed depth is something called the ‘horizon effect’. It might be that you have just captured an opponent’s pawn at depth 0, then you return that score being justifiably proud. However, if you had searched another ply deeper you would have seen that the opponent could recapture your queen! [Colin Frayn, Computer Chess Programming Theory, 2005. http://www.frayn.net/beowulf/theory.html]
Shannon-type-A tree of chess moves [Colin Frayn and Carlos Justiniano, The ChessBrain Project - Massively Distributed Chess Tree Search, Studies in Computational Intelligence (SCI) 71, 91–115 (2007)
Deferred thread cancellation was implemented by hand as OpenMP does not provide an ability a thread to cancel another thread from the outside. [Michael Sub and Claudia Leopold, Implementing Irregular Parallel Algorithms with OpenMP] Deferred cancellation is possible in POSIX threads as well. [POSIX standard, pthread_setcancelstate] Below is shown how deferred thread cancellation was implemented:
// parallel cancel threads workaround
if (IsCancelThreads)
break;
...
// parallel critical region: workaround a return clause
#pragma omp critical (ReturnResultFromThread)
{
if (!IsResultFound) {
ResultFromThread = CMSCORE - ply - 1;
IsResultFound = TRUE;
}
IsCancelThreads = TRUE;
} //includes implicit flush
if (IsCancelThreads)
break;
...
IsCancelThreads = TRUE;
#pragma omp flush (IsCancelThreads)
if (IsCancelThreads)
break;
...
Download the parallel open-source version of Beowulf (for Unix systems) from ParallelBeowulf.rar. (Change the file extension from ODT to RAR and unrar the archive. WordPress.com restricts file upload extensions.)
A set of 1285 Extended Position Description (EPD) Chess tests were ran toward the parallel and sequential Beowulf versions running on a same computer environment (CPU: AMD Opteron 64 Dual Core Processor 1.8 GHz RAM: 2GB 800 MHz HDD: 2x160GB Hitachi SATA in RAID 0 MB: Asus M2N-LR OS: Scientific Linux 5.3 64 bit Middleware: MPICH2 1.1.1p2). The compared results can be found here: sequential-output – parallel-output. After revealing the results it seems that the parallel version performs faster by examining many more moves (higher computational speed) but fails short in evaluating the best move. It took the parallel algorithm too much time to find the best move compared with the sequential Beowulf and in some of the test cases the time limit of half of a minute was not enough for the parallel Beowulf to find the correct move while the sequential algorithm succeeds.
EPD specifies the piece placement, the active color, the castling availability, and the en passant target square of a position. The castling availability field indicates potential future castling that may or may not be possible at the moment due to blocking pieces or enemy attacks. An EPD test contains a list (single or many items) of best moves which are compared with the algorithm’s best move in order to determine is the test passed or failed.
IDE Note: While Visual Studio 2008 and 2010 support OpenMP 2.0 for Visual C++, it is a shame that Visual Studio 2010 does not support OpenMP 3.0.
Ajax enabled web unfolds many new CSRF security problems
SPI Dynamics, Inc., a leading provider of web application security assessment software and services, which was acquired by HP in 2007, have revealed JavaScript techniques for compromising the intranet security of a user browsing hacker’s web page. Sadly, I have failed short to find an URL to the original paper but the hacking approach is explained in details in Martin Johns, A First Approach to Counter ”JavaScript Malware”, 2006.
The Intranet scanning scenario using JavaScript loaded in the browser from an ordinary Internet web site:
- The script constructs a local URL that contains the IP address and the port that shall be scanned.
- Then the script includes an element in the webpage that is addressed by this URL. Such elements can be, e.g., images, iframes or remote scripts.
- Using JavaScript’s time-out functions and eventhandlers like onload and onerror the script can decide whether the host exists and the given port is open: If a time-out occurs, the port is probably closed. If an onload- or onerror-event happens, the host answered with some data, indicating that the host is up and is listening on the targeted port.
The cross-domain networking capabilities of JavaScript are restricted by the Same origin policy (SOP). However, this policy allows including elements from cross domain http hosts into the DOM tree of the document that contains the JavaScript. This exception in the networking policy and the fact that the SOP applies on a document level creates a loophole in SOP.
A carefully crafted JavaScript code can port scan the intranet network of a web visitor and access its resources. Simply relying on the firewall to protect intranet http server against unauthorized access is not sufficient.
Nokia’s Qt Framework with an innovative mechanism of object communication
Qt Development Frameworks is a cross-platform application and UI framework on C++ from Nokia targeting mobile phone devices and many more. While most toolkits in C/C++ implement event-driven architecture with pointers to functions (callbacks), Qt provides an innovative Signals & Slots mechanism.
Back in 2008 I was developing a framework on C implementing a custom event-driven architecture relying on pointers to functions, and, thus, injecting type-unsafe conversions to void and backward.
CSRF on changing browser’s state
Attacks like malicious logging in the account of the hacker or other CSRF (Cross-Site Request Forgery) attacks causing browser state change have been newly decribed in the field of Internet security. Let’s describe a log-in CSRF. Many search engines, including Yahoo! and Google, allow their users to opt-in to saving their search history and provide an interface for a user to review his or her personal search history. Search queries contain sensitive details about the user’s interests and activities and could be used by an attacker to embarrass the user, to steal the user’s identity, or to spy on the user. An attacker can spy on a user’s search history by logging the user into the search engine as the attacker. The user’s search queries are then stored in the attacker’s search history, and the attacker can retrieve the queries by logging into his or her own account. [1]
An overwhelming amount of Internet sites change the browser’s state (mainly by setting a cookie) from insecure to CSRF HTML forms (using primarily GET, POST, or PUT methods) or even simple links (based on GET method). The HTML spec defines GET method among the safe methods as GET must not cause any side effects but simply retrieve information [2], but this is massively violated rule mainly in log-out links of web applications.
The modern trend in Internet applications is to keep track of the user preferences and to advise him to read/watch similar content, YouTube and Amazon to name only a few. Amazon.com sets a cookie for every search you perform with the aim to offer you a similar book to these you have searched for. Amazon articles can be loaded with GET methods. YouTube on his homepage will accumulate related content to the previously watched videos in it’s video sharing network. YouTube videos can be loaded with GET methods.
There will be some problems in performing such attack but it is irrefutable that most Internet applications change the browser’s state by insecure to CSRF requests. Such CSRF attacks unfold a potential for new spam techniques.
Many bussiness analysators rely on statistics on what users have searched on their sites, but it is important to note that such statistics can be powerfully manipulated by CSRF attacks. Forcing unaware web visitors to hidenly perform predefined searches on competitor’s web site can prevent a more clear vision of the current desires of the potential customers.
Cited sources:
1. Adam Barth, Collin Jackson, John C. Mitchell. Robust Defenses for Cross-Site Request Forgery, ACM 2007, 2007 Vol. Proceedings of the 15th ACM Conference on Computer and Communications Security, http://www.adambarth.com/papers/2008/barth-jackson-mitchell-b.pdf
2. Hypertext Transfer Protocol — HTTP/1.1, Section 9.1.1 Safe methods, 1991. http://www.w3.org/Protocols/rfc2616/rfc2616-sec9.html
CSRF on JSON data
A report on Cross-site Request Forgery on JavaScript Object Notation data can be downloaded from Garabedyan, CSRF on JSON data here (in Bulgarian only).
2010 review of the blog
The stats helper monkeys at WordPress.com mulled over how this blog did in 2010, and here’s a high level summary of its overall blog health:
The Blog-Health-o-Meter™ reads Minty-Fresh™.
Crunchy numbers
A helper monkey made this abstract painting, inspired by your stats.
A Boeing 747-400 passenger jet can hold 416 passengers. This blog was viewed about 1,300 times in 2010. That’s about 3 full 747s.
In 2010, there were 7 new posts, growing the total archive of this blog to 66 posts. There were 4 pictures uploaded, taking up a total of 103kb.
The busiest day of the year was October 20th with 24 views. The most popular post that day was My Research.
Where did they come from?
The top referring sites in 2010 were stackoverflow.com, jeremiahgrossman.blogspot.com, en.wordpress.com, bigextracash.com, and facebook.com.
Some visitors came searching, mostly for json vulnerabilities, norm judah, norm judah microsoft, garo garabedyan, and oops. your chat connection may have been interrupted.
Attractions in 2010
These are the posts and pages that got the most views in 2010.
My Research May 2007
1 comment
Object-Oriented Design Heuristics May 2009
1 comment
MetaOCaml-Resource Aware Programming May 2009
Norm Judah, CTO Microsoft Worldwide Services & IT, lecture in Bulgaria October 2009
1 comment
About the Author May 2007
