4 ms·

Okay, I used to work in anomaly detection, right, for more important server farms and networks, in particular for real-time, zero day detection, that is, detect

by graycat 10y ago

Okay, I used to work in anomaly detection, right, for more important server farms and networks, in particular for real-time, zero day detection, that is, detecting problems, anomalies, never seen before. The OP has 6 "ideal characteristics of a real-time anomaly detection algorithm". My work seems to do relatively well on the criteria. A challenging criterion is the 6th one: "The algorithm should minimize false positives and false negatives." So, no false positives and no false negatives would be a perfect detector, and in practice they are rarely possible. A more realistic formulation of the criterion is that for a given rate of false positives (false alarms) achieve the lowest rate possible for false negatives (missed detections of actual anomalies). How to do this is in the now classic Neyman-Pearson result. Right, in some cases the computations are a knapsack problem where that problem is, IIRC, in NP-complete. Really, another important criterion is to have the false alarm rate adjustable, that is, can set the false alarm rate in advance and get that rate exactly in practice. Yup, that's possible. Why? Really, anomaly detection is nearly necessarily some continuously (continually) applied statistical hypothesis tests where the null hypothesis is that the system being monitored, that is, the source of the data, is healthy and the data normal and not an anomaly or a symptom of a problem. So, we are into statistical hypothesis testing, and that is the context of the classic Neyman-Pearson result. The literature on statistical hypothesis testing goes back to at least the Neyman-Pearson result before 1950; the field is old with a lot known. In that field, it is usual to be able to set the rate of false alarms (type I error) in advance and get that rate exactly in practice. For monitoring server farms and networks, there are two additional criteria that are just crucial -- right, in particular for getting a low rate of missed detections (false negatives, type II errors) for a given rate of false positives: (1) Distribution-free. The easy way to be able to do the calculations of an hypothesis test is to assume that know the probability distribution of the input data when the null hypothesis holds. There, sure, the most common distribution assumed is the Gaussian. But there are also statistical hypothesis tests that are distribution-free (also non-parametric, e.g., not using the parameters of the Gaussian distribution) that is, that make no assumptions about the probability distribution of the data when the null hypothesis holds. For monitoring server farms and networks, too often should be using distribution-free tests. (2) Multi-dimensional The data readily available from monitoring server farms and networks is horrendously large, like flowing oceans of data. So, it's easy to get data on each of dozens of variables at rates from one point each few seconds up to hundreds of points a second. Treating such jointly multi-dimensional data one variable at a time must typically throw away a huge fraction of the relevant information. So, the data should be handled jointly. So, need statistical hypothesis tests that are multi-dimensional, and those are not so easy to find in the literature. So, the work I did for detecting zero-day problems in server farms and networks was to create a large collection of statistical hypothesis tests that are both distribution-free and multi-dimensional. E.g., if the data consists of a time series of points on a checkerboard and normal data is on the red squares, then my work will detect, with known and adjustable false alarm rate achieved exactly in practice, points on black squares. In this case, treating the data on each of two perpendicular edges (axes) of the checkerboard separately yields exactly nothing. So, this example illustrates the extra power of being multi-dimensional. Also the distribution of the data when the null hypothesis holds is just the red squares, that is, far from anything common in statistics. Moreover, can argue that there are some good qualitative reasons to believe that, really, a good detector for zero-day problems in server farms and networks should be able to know when it is in a fractal such as the Mandelbrot set and when not. Yes my work does that. But, I have to say, I did my work -- at IBM's Watson lab to improve on our approaches via AI -- and published it decades ago, and since then I've seen essentially no interest at all in the work. For more, for years I jerked the chains of a huge fraction of all the venture capital firms in the US with essentially no interest. My conclusion is good work in anomaly detection and a dime won't cover a ten cent cup of coffee. But, if by now anyone really is interested, then the remarks here should help.

d215 10y ago
I would be really interested to read the publication you did on this. We are trying to do anomaly detection from a large stream of traceroutes coming on from approx. 10,000 locations continuously over the internet.
- whatwasmypwd 10y ago
  I would also like to read this.
  - graycat 10y ago
    As in my https://news.ycombinator.com/user?id=graycat https://news.ycombinator.com/user?id=graycat here, somehow let me have an e-mail address.
    - d215 10y ago
      I left my email address in the `about` field of my hn profile.
      - graycat 10y ago
        Now you should have both the reference to the paper and a PDF of the paper. Thanks for your interest. Hope the paper is useful. My posts in this thread should help in reading the paper.
    - whatwasmypwd 10y ago
      I've included my email in the profile desc. Could you please also send this paper to me?
- graycat 10y ago
  Part I Here at HN I'm trying to be anonymous but on anomaly detection make a contribution. The basic idea of my research is for positive integer k, use k-nearest neighbors or, really, any of a wide variety of such measures, metrics, functions, windows however want to regard them. So, right, are on the way to some approaches to multi-dimensional probability density estimation. The main contribution of my research is the applied probability derivations to show how to calculate, adjust, set, etc. the false alarm rate. In practice, false alarm rate unknown, out'a control, often too high is a biggie problem -- e.g., can cause staff just to ignore too many alarms. E.g., see the movie Tora, Tora, Tora about the 12/7/1941 attack on Pearl Harbor where the US actually had just what the heck it needed for early detection, early enough to get fighter airplanes in the air, maybe early enough to get the ships out of the harbor, etc. -- radar on top of a hill. And the radar operators DID get the detection and DID report it, but the chain of command assumed that the detection was a false alarm. Big, huge, gigantic bummer. The US came within the thickness of an onion skin of getting the US airplanes and ships out of harm's way, shooting down much of the attacking airplanes, and having the US carriers, already at sea, attacking the attacking carriers when all their airplanes were off over Hawaii. The US could have sustained little damage and sunk all six of the attacking carriers. Having a good anomaly detector and ignoring it can be a bummer. But if know what the false alarm rate is and know that it's low, then maybe the chain of command will take a detection more seriously and, then, take the next step -- diagnosis. Sometimes the spook business, say, Soviets in England, would watch the comings, goings, lights on late, etc. at British military HQs and try to detect anomalies that would indicate war. Sure, for such detection need both distribution-free and multi-dimensional with good control over false alarm rate and good evidence of a relatively high detection rate. So, sure, the US CIA should want my work. I wrote them -- never heard back. Once I did give a talk on my work at the Institute for Defense Analysis (IDA), think tank resource for the Joint Chiefs. Some in the audience mentioned credit card fraud detection. Okay. But there should also be national security applications. Once gave a talk on the work at the Johns Hopkins University Applied Physics Lab (JHU/APL) -- I might as well have talked about a recipe for pancakes. Once I gave a talk on the work at the NASDAQ site in Trumbull, CT. I got a nice tour, a nice lunch, and a nice tote bag. I gave some talks on this work to my management chain at IBM's Watson lab -- the suits were afraid I might have some good work they didn't understand, couldn't control, and couldn't throttle. They were PISSED. I presented my work to some IBM people outside of Watson Research -- they liked the work, but Watson Research was PISSED. For the applied probability stuff in my research, for a detection of an anomaly can also report the lowest false alarm rate at which the data would still be a detection. Then right along can graph these lowest rates and use them as a heuristic about detection seriousness. Net, getting a handle, knob to turn, knowledge of, etc. false alarm rate is important. The applied probability stuff is based on some cute symmetry in the calculations. The symmetry, then, gives some measure preserving transformations (transformations that don't change the probability distribution). So, end up with a finite algebraic group of such transformations. Then sum over the group and, presto, bingo, get what need to know false alarm rate. To adjust the false alarm rate, adjust the diameter, cut-off, whatever, of the k nearest neighbors or other metric, convolution window, etc. Of course all of this is conditional probabilities conditioned on the historical data used where assume that the system being monitored when the historical data was collected was healthy. How to confirm healthy? Let the data age and see if there are any other, later symptoms of problems from other means, e.g., angry customer complaints, malware, attacks and intrusions, etc. So, have a case of, essentially, being brief here, the conditional expectation E[Y|X] where Y is the random variable of detections and X is the historical data. Then of course E[E[Y|X]] = E[Y] which says that have set false alarm rate "exactly" in the long-run or, if you will, conditionally exactly in the short run. A result is that the naive way to evaluate false alarm rate from the historical data does, for lots of data, converge to the right answer. Proving that, however, was a bit tricky. Achieving the Neyman-Pearson best result needs lots of data from both healthy and sick systems, and in practice the second is in short supply. The Neyman-Pearson result is intuitive, like investing in real estate: Buy plots of real estate that give the best return per dollar invested until have invested all the available money. Well, suppose the data observed is, for the set of real numbers R and some positive integer n, in R^n. Then partition R^n into little patches. Then in each little patch, assume that data in that patch would raise an alarm, and, then, from the data (need lots of data, especially as n grows) get the ratio of the detection rate over the false alarm rate. Then false alarm rate is really like the money you have to invest, and detection rate is your return on that investment. So, sure, you buy the patches with the highest ratio until you have spent, invested, all your false alarm rate, money. Can find proofs in terms of freshman calculus. I wrote out a quite general proof in terms of the Hahn decomposition from the Radon-Nikodym theorem in measure theory. So, right, if have only finitely many patches in R^n, then have essentially a knapsack problem, IIRC, in NP-complete (although likely not a concern in practice). Can write out a little derivation, mostly just Fubini's theorem (the measure theory version of the calculus interchange order of integration) to show in a cute sense of the distribution of sick systems being translation invariant (right, a bit much to assume -- but here I'm typing quickly from memory of what I did 20+ years ago) then my techniques give, for the assumed false alarm rate, the highest detection rate possible. So, this is a simple, quick and dirty, data-free, crude approach to the full Neyman-Pearson result of best detection.

by graycat 10y ago

d215 10y ago

I would be really interested to read the publication you did on this. We are trying to do anomaly detection from a large stream of traceroutes coming on from approx. 10,000 locations continuously over the internet.

whatwasmypwd 10y ago
I would also like to read this.
- graycat 10y ago
  As in my https://news.ycombinator.com/user?id=graycat https://news.ycombinator.com/user?id=graycat here, somehow let me have an e-mail address.
  - d215 10y ago
    I left my email address in the `about` field of my hn profile.
    - graycat 10y ago
      Now you should have both the reference to the paper and a PDF of the paper. Thanks for your interest. Hope the paper is useful. My posts in this thread should help in reading the paper.
  - whatwasmypwd 10y ago
    I've included my email in the profile desc. Could you please also send this paper to me?
graycat 10y ago
Part I Here at HN I'm trying to be anonymous but on anomaly detection make a contribution. The basic idea of my research is for positive integer k, use k-nearest neighbors or, really, any of a wide variety of such measures, metrics, functions, windows however want to regard them. So, right, are on the way to some approaches to multi-dimensional probability density estimation. The main contribution of my research is the applied probability derivations to show how to calculate, adjust, set, etc. the false alarm rate. In practice, false alarm rate unknown, out'a control, often too high is a biggie problem -- e.g., can cause staff just to ignore too many alarms. E.g., see the movie Tora, Tora, Tora about the 12/7/1941 attack on Pearl Harbor where the US actually had just what the heck it needed for early detection, early enough to get fighter airplanes in the air, maybe early enough to get the ships out of the harbor, etc. -- radar on top of a hill. And the radar operators DID get the detection and DID report it, but the chain of command assumed that the detection was a false alarm. Big, huge, gigantic bummer. The US came within the thickness of an onion skin of getting the US airplanes and ships out of harm's way, shooting down much of the attacking airplanes, and having the US carriers, already at sea, attacking the attacking carriers when all their airplanes were off over Hawaii. The US could have sustained little damage and sunk all six of the attacking carriers. Having a good anomaly detector and ignoring it can be a bummer. But if know what the false alarm rate is and know that it's low, then maybe the chain of command will take a detection more seriously and, then, take the next step -- diagnosis. Sometimes the spook business, say, Soviets in England, would watch the comings, goings, lights on late, etc. at British military HQs and try to detect anomalies that would indicate war. Sure, for such detection need both distribution-free and multi-dimensional with good control over false alarm rate and good evidence of a relatively high detection rate. So, sure, the US CIA should want my work. I wrote them -- never heard back. Once I did give a talk on my work at the Institute for Defense Analysis (IDA), think tank resource for the Joint Chiefs. Some in the audience mentioned credit card fraud detection. Okay. But there should also be national security applications. Once gave a talk on the work at the Johns Hopkins University Applied Physics Lab (JHU/APL) -- I might as well have talked about a recipe for pancakes. Once I gave a talk on the work at the NASDAQ site in Trumbull, CT. I got a nice tour, a nice lunch, and a nice tote bag. I gave some talks on this work to my management chain at IBM's Watson lab -- the suits were afraid I might have some good work they didn't understand, couldn't control, and couldn't throttle. They were PISSED. I presented my work to some IBM people outside of Watson Research -- they liked the work, but Watson Research was PISSED. For the applied probability stuff in my research, for a detection of an anomaly can also report the lowest false alarm rate at which the data would still be a detection. Then right along can graph these lowest rates and use them as a heuristic about detection seriousness. Net, getting a handle, knob to turn, knowledge of, etc. false alarm rate is important. The applied probability stuff is based on some cute symmetry in the calculations. The symmetry, then, gives some measure preserving transformations (transformations that don't change the probability distribution). So, end up with a finite algebraic group of such transformations. Then sum over the group and, presto, bingo, get what need to know false alarm rate. To adjust the false alarm rate, adjust the diameter, cut-off, whatever, of the k nearest neighbors or other metric, convolution window, etc. Of course all of this is conditional probabilities conditioned on the historical data used where assume that the system being monitored when the historical data was collected was healthy. How to confirm healthy? Let the data age and see if there are any other, later symptoms of problems from other means, e.g., angry customer complaints, malware, attacks and intrusions, etc. So, have a case of, essentially, being brief here, the conditional expectation E[Y|X] where Y is the random variable of detections and X is the historical data. Then of course E[E[Y|X]] = E[Y] which says that have set false alarm rate "exactly" in the long-run or, if you will, conditionally exactly in the short run. A result is that the naive way to evaluate false alarm rate from the historical data does, for lots of data, converge to the right answer. Proving that, however, was a bit tricky. Achieving the Neyman-Pearson best result needs lots of data from both healthy and sick systems, and in practice the second is in short supply. The Neyman-Pearson result is intuitive, like investing in real estate: Buy plots of real estate that give the best return per dollar invested until have invested all the available money. Well, suppose the data observed is, for the set of real numbers R and some positive integer n, in R^n. Then partition R^n into little patches. Then in each little patch, assume that data in that patch would raise an alarm, and, then, from the data (need lots of data, especially as n grows) get the ratio of the detection rate over the false alarm rate. Then false alarm rate is really like the money you have to invest, and detection rate is your return on that investment. So, sure, you buy the patches with the highest ratio until you have spent, invested, all your false alarm rate, money. Can find proofs in terms of freshman calculus. I wrote out a quite general proof in terms of the Hahn decomposition from the Radon-Nikodym theorem in measure theory. So, right, if have only finitely many patches in R^n, then have essentially a knapsack problem, IIRC, in NP-complete (although likely not a concern in practice). Can write out a little derivation, mostly just Fubini's theorem (the measure theory version of the calculus interchange order of integration) to show in a cute sense of the distribution of sick systems being translation invariant (right, a bit much to assume -- but here I'm typing quickly from memory of what I did 20+ years ago) then my techniques give, for the assumed false alarm rate, the highest detection rate possible. So, this is a simple, quick and dirty, data-free, crude approach to the full Neyman-Pearson result of best detection.