Senin, 11 Juni 2012
This post discusses the entropy-plotting tool ent . The post will be updated as its status progresses (see future).
Application:
My interest came from a better plotting measure for the recently released password-hash files in regard of its peculiar hash character structure.
1st Example
2nd Example:
Applied to the CC-By-SA png file (
) the resulting plot is as follows:
Please note that at the present, I am unaware of another tool plotting the permutation entropy. If you are, please let it be known in the comments.
Theory:
The permutation entropy of order n >= 2 is defined as:
Given a sequence, all n! permutations π of order n (e.g. n different numbers) are determined.For each π in S n we determine the relative frequency as:
Then calculation of the typical shannon entropy will yield the permutation entropy measure:
with the sum running over all n! permutations π of order n.
It is quite trivial to compute and thus fast.
Future
Google's endeavor as well as those of many other big companies towards web-based application usage and cloud computing, naturally concerns me as an application developer. Striking to me was Google's change in attitude towards bringing the Chrome browser, in its entirety, to its widely successful Android platform. Such a move was considered unlikely just two years ago.
It is my intend to bring ent to the web. Challenging herein is the creation of an intuitive user interface, that whilst simple to use, provides assertive information in an on-the-fly browsing fashion. The FileReader API makes segmented-reading of files on the order of gigabytes a breeze. A javascript task within a web-worker and its own memory context should do the job fast enough to be usable as a replacement to Ent.
Entropy is a physical property which we are all intuitively familiar with, yet many of us may find themselves hard pressed to put entropy into precise terms. A similar challenge applies to the design of a web-application user-interface for Ent that captures and carries over this intuitiveness. Yet that challenge makes a web-port inherently enticing.
Following is a list of coming updates.
[1] Permutation Entropy – a natural complexity measure for time series, Christoph Bandt, Bernd Pompe. Physical Review Letters, Vol. 88, No. 17. (April 2002)
Permutation entropies are appropriate complexity measures for chaotic time series, in particular in the presence of dynamical and observational noise. In contrast with all known complexity parameters, a small noise does not essentially change the complexity of a chaotic signal.[1]It is not often that I start with the conclusion from a paper. The quote is from the paper Permutation Entropy – a natural complexity measure for time series. Permutation entropy has been frequently applied to dynamic systems as a robust measure of complexity characterization. As such it is applied to gene expression and in this case to detect changes in hash password complexity (Fig 1.1). The calculation and plotting of the permutation entropy of an arbitrary character sequence is now possible through the command-line tool Ent (Download).
Application:
My interest came from a better plotting measure for the recently released password-hash files in regard of its peculiar hash character structure.
1st Example
 |
| Fig 1.1. Showing a normalized Shannon-Entropy Plot with an log-base relative to the number of different characters over the entire file, and below, a Permutation Entropy plot of a permutation order of 2, using a binary base. The drop in entropy is caused by a change (unmasked?) hash-sequence (See below). |
 |
| Change in of the first five characters of the SHA1 LinkedIn hashes |
Applied to the CC-By-SA png file (
) the resulting plot is as follows: |
| Fig 1.2 Showing the expected difference of a shannon entropy plot (top) and a permutation entropy plot (bottom) as a measure of complexity change of the 728Byte CC-BY-SA png-logo file. Owing to the file structure of the png-format, the entropy varies for small files with a narrow color-index table. There is no discernible interdependency of the character sequence, as can be seen in the permutation entropy plot (bottom). |
Please note that at the present, I am unaware of another tool plotting the permutation entropy. If you are, please let it be known in the comments.
Theory:
The permutation entropy of order n >= 2 is defined as:
Given a sequence, all n! permutations π of order n (e.g. n different numbers) are determined.For each π in S n we determine the relative frequency as:
It is quite trivial to compute and thus fast.
Future
Google's endeavor as well as those of many other big companies towards web-based application usage and cloud computing, naturally concerns me as an application developer. Striking to me was Google's change in attitude towards bringing the Chrome browser, in its entirety, to its widely successful Android platform. Such a move was considered unlikely just two years ago.
It is my intend to bring ent to the web. Challenging herein is the creation of an intuitive user interface, that whilst simple to use, provides assertive information in an on-the-fly browsing fashion. The FileReader API makes segmented-reading of files on the order of gigabytes a breeze. A javascript task within a web-worker and its own memory context should do the job fast enough to be usable as a replacement to Ent.
Entropy is a physical property which we are all intuitively familiar with, yet many of us may find themselves hard pressed to put entropy into precise terms. A similar challenge applies to the design of a web-application user-interface for Ent that captures and carries over this intuitiveness. Yet that challenge makes a web-port inherently enticing.
Following is a list of coming updates.
- Proper Readme, source cleanup (status: in progress; will be put on github soon)
- Scrolling through files - (status: works; pressing 'q' quits Ent)
- Port to a web-tool based on JSIL, and a Chrome Browser Extension (status: over the coming months)
- Eventually, specificity parameters for number sequences and biological sequences
[1] Permutation Entropy – a natural complexity measure for time series, Christoph Bandt, Bernd Pompe. Physical Review Letters, Vol. 88, No. 17. (April 2002)