General malware detectors are impossible

It is impossible to write a general purpose malware detector. Not hard, not difficult, impossible. The argument for the impossibility relies on building an odd program. We may not write such a program in practice, but it does arise as a combination of things we do write — things like Perl-like regular expressions and input parsers — and carefully crafted inputs. The type of malware we often worry about is the type that alters the environment of the CPU.…

Keep reading

More on the curse

The n-cube playground As a playground to understand the curse of dimensionality we spread 20,000 points throughout a 10-dimensional cube of side 2. Each coordinate of a point is independently chosen from a uniform random distribution ranging from -1 to 1. While the points are uniform in the ten dimensional cube, that will not be the case if we project them along a line that crosses the center of the cube The points appear to be concentrated near the middle of the line.…

Keep reading

The two curses of dimensionality

The muse of geometry has cast two curses on our computers. We have all felt the one Bellman wrote about, but the other stands there like Cassandra awaiting our use of statistical methods. The curse of dimensionality made its print appearance in Richard Bellman’s 1957 book Dynamic programming. It was an outcry over the impossibilities of dealing with functions of many variables when a million bytes of memory seemed beyond imagination.…

Keep reading

Given a wall, who wins?

Walls guard. Walls constrain. They defy us to break them. And so it has been since the dawn of agriculture. We see defensive walls protecting ancient cities from China through sub-Saharan Africa. Their widespread prevalence is a testment of their desirability. A wall around a city correlated well with the size of its merchant community, protecting the riches within from the ravages of medieval times while providing an overt display of the city’s wealth, power, and organizational skills.…

Keep reading

Markov's bound

I find it much easier to understand math from another person than from just reading it. One of my theories of why, is that the painful and tortuous way something gets understood is not the way it gets written up. In an attempt to expose that even simple things are not always that obvious, I captured the path I had taken while noodling over the Markov inequality by going over all the paper in my wastebasket.…

Keep reading